#x1030. CF164C Machine Programming

    ID: 5983 远端评测题 5000ms 256MiB 尝试: 1 已通过: 0 难度: 7 上传者: 标签>CF2200提高+/省选-指定流量最小费用流离散化势能优化费用流DijkstraDAG 动态规划残量网络半开区间统一费用流2400

CF164C Machine Programming

Machine Programming

题面翻译

题目描述:

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

输入格式:

第一行为两个整数 n (1≤n≤1000)n\ (1\le n\le 1000),k (≤k≤50)k\ (\le k\le50) 。nn 和 kk 分别代表任务数量和机器数量。

接下来 nn 行每行三个整数 si,ti,cis_i,t_i,c_i (1≤si,ti≤109,1≤ci≤106)(1\le s_i,t_i\le10^9,1\le c_i\le10^6),含义如描述。

输出格式:

输出 nn 个数字 x1,x2,...,xnx_{1},x_{2},...,x_{n},以空格相隔。数字 xix_i 为 11 或 00 ,11 代表选择任务 ii,00 代表不选择。 如果有多个选择方案,输出任何一个即可。

by lyh

题目描述

One remarkable day company "X" received k 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 n tasks, for each of them we know the start time of its execution si s_{i} , the duration of its execution ti t_{i} , and the company profit from its completion ci 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 si s_{i} to si+ti−1 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 k machines, and which will bring the maximum total profit.

输入格式

The first line contains two integer numbers n n and k k ( 1<=n<=1000 1<=n<=1000 , 1<=k<=50 1<=k<=50 ) — the numbers of tasks and machines, correspondingly.

The next n n lines contain space-separated groups of three integers si,ti,ci s_{i},t_{i},c_{i} ( 1<=si,ti<=109 1<=s_{i},t_{i}<=10^{9} , 1<=ci<=106 1<=c_{i}<=10^{6} ), si s_{i} is the time where they start executing the i i -th task, ti t_{i} is the duration of the i i -th task and ci c_{i} is the profit of its execution.

输出格式

Print n n integers x1,x2,...,xn x_{1},x_{2},...,x_{n} . Number xi x_{i} should equal 1 1 , if task i i should be completed and otherwise it should equal 0 0 .

If there are several optimal solutions, print any of them.

样例 #1

样例输入 #1

3 1
2 7 5
1 3 3
4 1 3

样例输出 #1

0 1 1

样例 #2

样例输入 #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).