Рейтинг студента Условие

Многие вузы переходят на рейтинговую систему оценки: оценки студентов зависят от того, как они сдают задания в течение всего семестра. Для каждого задания устанавливается срок сдачи, позже которого задание не принимается.

Один студент получил N заданий утром дня с номером 1.

• Студенту потребуется ровно L_i дней, чтобы выполнить задание с номером i.

• Если студент берётся за какое-либо задание, то он ни на что не будет отвлекаться, пока его не выполнит.

• Начав работать над заданием в день с номером x, студент закончит и сдаст его в день с номером x + L_i − 1. Силы взяться за новое задание будут у него только на следующий день.

• Задание с номером i не будет принято, если оно будет сдано позже, чем в день с номером D_i.

• Рейтинг студента увеличится на R_i баллов после сдачи задания с номером i.

Студент хочет, чтобы его рейтинг стал как можно выше. Напишите программу, которая, получив информацию о заданиях, определит, какие задания и в каком порядке должен выполнять студент, чтобы максимально повысить свой рейтинг.

Формат входного файла

Входной файл содержит целое число N, за которым следует N троек целых чисел L_i D_i R_i — информация о заданиях.

Формат выходного файла

Программа должна вывести в выходной файл максимальное количество баллов, которое может заработать студент, а затем — описания заданий, которые ему нужно для этого выполнить. Каждое описание состоит из чисел k_i s_i — порядкового номера задания и номера дня, когда студенту нужно начать его выполнение. Все k_i должны быть различны. Задания должны быть выведены в порядке возрастания s_i.

Если студент не сможет заработать ни одного балла, вывести единственное число 0.

Если существует несколько способов заработать максимальное количество баллов, вывести любой из них.

Ограничения

1 ≤ N ≤ 1000

1 ≤ L_i, D_i, R_i ≤ 1000

Примеры тестов

№	Входной файл	Выходной файл
1	5 7 8 6 2 2 1 5 8 4 3 9 3 2 5 1	7 3 1 4 6

Разбор

Заметим, что если студент уже выбрал, какие задания он будет выполнять, то он может выполнять их в порядке возрастания D_i. Такой порядок является оптимальным в том смысле, что при замене любого другого порядка выполнения заданий на этот порядок ситуация не ухудшится: если при другом порядке студент укладывался в сроки, то при таком порядке он тем более уложится в сроки. Следовательно, будем искать решение в таком виде: пусть студент выполняет задания в порядке возрастания D_i.

Применим метод динамического программирования. Предварительно упорядочим задания по возрастанию D_i. Подзадача с параметрами (i, j): пусть студент выполнил какие-то задания из заданий с 1-го по i-е и потратил на выполнение заданий j дней. Пусть c(i, j) — решение подзадачи с параметрами (i, j). Для вывода рекуррентного соотношения заметим, что студент мог либо выполнить i-е задание, либо нет. Рекуррентное соотношение:

c(i, j) = max{c(i – 1, j), c(i – 1, j – L_i) + R_i}.

program rating;

const

maxN = 1000;

maxD = 2000;

var

c, p: array[0..maxN, 0..maxD] of integer;

d, r, l: array[1..maxN] of integer;

num: array[1..maxN] of integer;

n: integer;

res, best: integer;

i, j: integer;

function max(a, b: integer): integer;

begin

if (a > b) then

Result := a

else

Result := b;

end;

procedure swapint(var a, b: integer);

var

tmp: integer;

begin

tmp := a;

a := b;

b := tmp;

end;

procedure rec(i, j: integer);

begin

if (p[i-1, j-l[i]] <> 0) then

rec(p[i-1, j-l[i]], j-l[i]);

writeln(num[i], ' ', j-l[i]+1);

end;

begin

assign(input, 'input.txt');

reset(input);

assign(output, 'output.txt');

rewrite(output);

read(n);

for i := 1 to n do

begin

read(l[i], d[i], r[i]);

num[i] := i;

end;

for i := 1 to n do

begin

for j := i+1 to n do

begin

if (d[i] > d[j]) then

begin

swapint(d[i], d[j]);

swapint(r[i], r[j]);

swapint(l[i], l[j]);

swapint(num[i], num[j]);

end;

end;

end;

FillChar(c, SizeOf(c), 0);

FillChar(p, SizeOf(p), 0);

for i := 1 to n do

begin

for j := 1 to maxD do

begin

c[i, j] := c[i-1, j];

p[i, j] := p[i-1, j];

if (j >= l[i]) and (j <= d[i]) then

begin

if (c[i-1, j-l[i]]+r[i] > c[i, j]) then

begin

c[i, j] := c[i-1, j-l[i]]+r[i];

p[i, j] := i;

end;

end;

end;

end;

res := 0;

best := 0;

for i := 1 to maxD do

begin

if (c[n, i] > res) then

begin

res := c[n, i];

best := i;

end;

end;

writeln(res);

if (res > 0) then

rec(p[n, best], best);

close(input);

close(output);

end.