Решение задачи "Деву-дурачок" с Codeforces

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


Деву — дурачок и учится очень медленно. Вам надо научить его n дисциплинам, i-я дисциплина состоит из c i частей, при этом для изучения дисциплины, нужно последовательно изучить все ее части.

Изначально «способность усвоения знаний» Деву равна x часов. Иными словами, он может усвоить любую часть некоторой дисциплины за x часов.

Впрочем, Деву не полный дурак — есть на что надеяться. Если вы обучите его какой-то дисциплине, то для изучения каждой части следующей дисциплины потребуется ровно на один час меньше, чем раньше (для лучшего понимания смотрите примеры). Обратите внимание, что его способность усвоения не может быть менее 1 часа.

Вы можете обучать его дисциплинам в любом порядке. Подсчитайте наименьшее количество времени (в часах), необходимое Деву для усвоения всех n дисциплин — и тогда можно будет порешать более интересные задачи, а не нянчиться с дурачком.

Пожалуйста, будьте внимательны — ответ может превысить 32-битный целочисленный тип данных.

Код

#include<bits/stdc++.h>
using namespace std;
long long n,x,a[200000],ans;
int main()
{
	cin>>n>>x;
	for(int i=0;i<n;i++)
		cin>>a[i];
	sort(a,a+n);
	for(int i=0;i<n;i++)
	{
		ans+=a[i]*x;
		x=max((long long)1,--x);
	}
	cout<<ans;
	return 0;
}

         

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


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

Комментарии

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