CF164C Machine Programming

有一家公司有 $k$ 台机器，并且有 $n$ 个任务需要完成，对于每一个任务我们知道它的开始时间 $s_i$ 和持续时间 $t_i$ ,并且完成这个任务后这家公司可以获利 $c_i$ 。每一台机器都可以处理任何任务，但不能同时处理多个任务，在处理某个任务时也不能切换到其他任务（即当某个机器处理任务 $i$ 时，在 $s_i$ 至 $s_i+t_i-1$ 时间段内就只能处理这个任务）。你需要选择一些任务来完成，使得总利润最大。

第一行为两个整数 $n\ (1\le n\le 1000)$，$k\ (\le k\le50)$ 。$n$ 和 $k$ 分别代表任务数量和机器数量。 接下来 $n$ 行每行三个整数 $s_i,t_i,c_i$ $(1\le s_i,t_i\le10^9,1\le c_i\le10^6)$，含义如描述。

输出 $n$ 个数字 $x_{1},x_{2},...,x_{n}$，以空格相隔。数字 $x_i$ 为 $1$ 或 $0$ ，$1$ 代表选择任务 $i$，$0$ 代表不选择。 如果有多个选择方案，输出任何一个即可。 by [lyh](/user/505244)

In the first sample the tasks need to be executed at moments of time 2 ... 8, 1 ... 3 and 4 ... 4, correspondingly. The first task overlaps with the second and the third ones, so we can execute either task one (profit 5) or tasks two and three (profit 6).