Решение задачи "Девочка и максимальная сумма" с Codeforces

Без пояснения   Просмотров: 18

Девочка очень любит задачи про запросы на массиве.

Однажды ей попалась довольно известная задача: дан массив из n элементов (элементы массива проиндексированы от 1); также есть q запросов, каждый из которых задается парой целых чисел l i, r i (1 ≤ l i ≤ r i ≤ n). Для каждого запроса необходимо найти сумму всех элементов массива с индексами от l i до r i включительно.

Такая задача показалась Девочке довольно скучной. Она решила, что перед тем, как отвечать на запросы, она перемешает элементы массива, причем так, чтобы сумма ответов на все запросы была максимально возможной. Ваша задача — найти значение этой максимальной суммы.

Код 

#include<bits/stdc++.h>

using namespace std;

int main()
{
	int n, q;
	cin >> n >> q;
	int a[n], cnt[n + 1] = { 0 };
	for( int i = 0; i < n; i++ ) cin >> a[i];
	sort( a, a + n );
	while( q-- ){
		int l, r;
		cin >> l >> r;
		l--;
		r--;
		cnt[l]++;
		cnt[r + 1]--;
	}
	for( int i = 1; i < n; i++ ) cnt[i] += cnt[i - 1];
	sort( cnt, cnt + n );
	long long ans = 0;
	for( int i = n - 1; i >= 0; i-- )
		ans += 1ll * cnt[i] * a[i];
	cout << ans << endl;
}

         

<div style=

A PHP Error was encountered

Severity: Notice

Message: Undefined index: first_name

Filename: templates/tasksdecision_view.php

Line Number: 133

Backtrace:

File: /var/www/u0984434/data/www/hsecodes.com/application/views/templates/tasksdecision_view.php
Line: 133
Function: _error_handler

File: /var/www/u0984434/data/www/hsecodes.com/application/controllers/Tasksdecision.php
Line: 120
Function: view

File: /var/www/u0984434/data/www/hsecodes.com/index.php
Line: 315
Function: require_once

Администратор Photo" /> Автор:


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться