#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define START 0
#define END 1
#define MONEY 2
#define N_L 10
#define M_L 11
int taskN, day;
int task[N_L][3];
int money[M_L];
void init()
{
}
void input()
{
scanf("%d %d", &taskN, &day);
for (int i = 1; i <= taskN; i++)
{
scanf("%d %d %d", &task[i][START], &task[i][END], &task[i][MONEY]);
}
}
void swap(int a, int b)
{
int start = task[a][START];
int end = task[a][END];
int money = task[a][MONEY];
task[a][START] = task[b][START];
task[a][END] = task[b][END];
task[a][MONEY] = task[b][MONEY];
task[b][START] = start;
task[b][END] = end;
task[b][MONEY] = money;
}
void qsort(int left, int right)
{
if (left < right)
{
int p = left;
int p_val = task[right][END];
for (int i = left; i < right; i++)
{
if (task[i][END] <= p_val)
swap(p++, i);
}
swap(p, right);
qsort(left, p - 1);
qsort(p + 1, right);
}
}
void solve()
{
qsort(1, taskN);
int tn = 1;
money[0] = 0;
for (int d = 1; d <= day; d++)
{
int maxMoney = money[d - 1];
while (task[tn][END] == d)
{
int m = task[tn][MONEY] + money[task[tn][START] - 1];
if (maxMoney < m)
maxMoney = m;
tn++;
}
money[d] = maxMoney;
}
printf("%d", money[day]);
}
int main(void)
{
freopen("input.txt", "r", stdin);
int test_case;
int T;
setbuf(stdout, NULL);
scanf("%d", &T);
for (test_case = 1; test_case <= T; ++test_case)
{
printf("#%d ", test_case);
init();
input();
solve();
printf("\n");
}
return 0;
}
댓글