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)

题目描述

One remarkable day company "X" received $ k $ machines. And they were not simple machines, they were mechanical programmers! This was the last unsuccessful step before switching to android programmers, but that's another story. The company has now $ n $ tasks, for each of them we know the start time of its execution $ s_{i} $ , the duration of its execution $ t_{i} $ , and the company profit from its completion $ c_{i} $ . Any machine can perform any task, exactly one at a time. If a machine has started to perform the task, it is busy at all moments of time from $ s_{i} $ to $ s_{i}+t_{i}-1 $ , inclusive, and it cannot switch to another task. You are required to select a set of tasks which can be done with these $ k $ machines, and which will bring the maximum total profit.

输入输出格式

输入格式

The first line contains two integer numbers $ n $ and $ k $ ( $ 1<=n<=1000 $ , $ 1<=k<=50 $ ) — the numbers of tasks and machines, correspondingly. The next $ n $ lines contain space-separated groups of three integers $ s_{i},t_{i},c_{i} $ ( $ 1<=s_{i},t_{i}<=10^{9} $ , $ 1<=c_{i}<=10^{6} $ ), $ s_{i} $ is the time where they start executing the $ i $ -th task, $ t_{i} $ is the duration of the $ i $ -th task and $ c_{i} $ is the profit of its execution.

输出格式

Print $ n $ integers $ x_{1},x_{2},...,x_{n} $ . Number $ x_{i} $ should equal $ 1 $ , if task $ i $ should be completed and otherwise it should equal $ 0 $ . If there are several optimal solutions, print any of them.

输入输出样例

输入样例 #1

3 1
2 7 5
1 3 3
4 1 3

输出样例 #1

0 1 1

输入样例 #2

5 2
1 5 4
1 4 5
1 3 2
4 1 2
5 6 1

输出样例 #2

1 1 0 0 1

说明

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).