Вася учится в 10 классе тридевятой школы и мечтает победить в турнире <Экспонента>.
Этот турнир проводится ежегодно в апреле.
Участвовать в нём могут школьники и студенты.
Вася понимает, что пока ещё недостаточно подготовлен для победы, но готов упорно тренироваться.
Он нашёл в Интернете N задач, для каждой из которых известна её полезность.
Полезность задачи равна количеству наномитричей, на которое её решение увеличивает силу программиста.
К сожалению, Вася не может всё своё время посвятить тренировкам (причины этого вам хорошо известны), так что за оставшиеся до турнира дни он успеет решить только K задач.
Напишите программу, которая по заданным N, K и полезностям задач в наномитричах Mi, i = 1, ..., N вычисляет силу, которую успеет набрать Вася к турниру <Экспонента>.
Исходная сила Васи равна одному наномитричу.
Вход
В первой строке входного файла записаны два целых числа N и K (0 <= N, K <= 10^5).
Во второй строке файла записаны N целых чисел - полезности задач M(1), ..., M(N) (0 <= M(i) <= 10^8).
Выход
Запишите в выходной файл наибольшую силу в наномитричах, которую Вася успеет набрать до турнира <Экспонента>.
Гарантируется, что результат не превысит 1 митрича.
Замечание
Единица программистской силы наномитрич равна 10^-9 митрича.
Один митрич равен силе знаменитого программиста Петра Митричева.
Этот турнир проводится ежегодно в апреле.
Участвовать в нём могут школьники и студенты.
Вася понимает, что пока ещё недостаточно подготовлен для победы, но готов упорно тренироваться.
Он нашёл в Интернете N задач, для каждой из которых известна её полезность.
Полезность задачи равна количеству наномитричей, на которое её решение увеличивает силу программиста.
К сожалению, Вася не может всё своё время посвятить тренировкам (причины этого вам хорошо известны), так что за оставшиеся до турнира дни он успеет решить только K задач.
Напишите программу, которая по заданным N, K и полезностям задач в наномитричах Mi, i = 1, ..., N вычисляет силу, которую успеет набрать Вася к турниру <Экспонента>.
Исходная сила Васи равна одному наномитричу.
Вход
В первой строке входного файла записаны два целых числа N и K (0 <= N, K <= 10^5).
Во второй строке файла записаны N целых чисел - полезности задач M(1), ..., M(N) (0 <= M(i) <= 10^8).
Выход
Запишите в выходной файл наибольшую силу в наномитричах, которую Вася успеет набрать до турнира <Экспонента>.
Гарантируется, что результат не превысит 1 митрича.
Замечание
Единица программистской силы наномитрич равна 10^-9 митрича.
Один митрич равен силе знаменитого программиста Петра Митричева.
More Questions From This User See All
Answers & Comments
#include <algorithm>
using namespace std;
const int N = 1e5 + 3;
int m[N];
int main()
{
int n, k;
cin >> n >> k;
k = min(k, n);
for (int i = 0; i < n; ++i)
cin >> m[i];
sort(m, m + n);
reverse(m, m + n);
int ans = 1;
for (int i = 0; i < k; ++i)
ans += m[i];
cout << ans << endl;
return 0;
}