Решение задачи Тренировка Поликарпа с Codeforces

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


Поликарп тренирует свое умение решать задачи. У него есть список из n задач со сложностями a1,a2,…,an соответственно. Его план состоит в том, чтобы тренироваться ровно k дней. Каждый день он должен решать хотя бы одну задачу из своего списка. Поликарп решает задачи в том порядке, в котором они заданы в списке, и он не может пропустить какую-либо задачу из списка. Он должен решить ровно n задач ровно за k дней.

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

Полезность j-го дня тренировки Поликарпа равна максимальной сложности задачи среди всех задач, которые Поликарп решит в течение j-го дня (то есть если он решит задачи с номерами от l до r в течение какого-то дня, тогда полезность этого дня равна maxl≤i≤rai). Общая полезность его тренировки — это сумма полезностей по всем k дням его тренировки.

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

Например, если n=8,k=3 и a=[5,4,2,6,5,1,9,2], одним из возможных способов с максимальной общей полезностью является следующий: [5,4,2],[6,5],[1,9,2]. Здесь общая полезность равна 5+6+9=20.

Код

// practice with Dukkha
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 2000;

int aa[N], ii[N];

int main() {
	int n, k; cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> aa[i];
		ii[i] = i;
	}
	sort(ii, ii + n, [] (int i, int j) { return aa[i] > aa[j]; });
	int a = 0;
	for (int i = 0; i < k; i++)
		a += aa[ii[i]];
	cout << a << '\n';
	sort(ii, ii + k);
	int i_ = -1;
	for (int i = 0; i < k - 1; i++) {
		cout << ii[i] - i_ << ' ';
		i_ = ii[i];
	}
	cout << n - 1 - i_ << '\n';
	return 0;
}

         

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



Комментарии

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