0 人解决，3 人已尝试。
0 份提交通过，共有 3 份提交。
9.9 EMB 奖励。
2608. Battle of Submarines
单点时限: 2.0 sec
内存限制: 256 MB
A ship is on a W wide sea area. N enemy submarines numbered from 1 to N are underwater moving from west to east at
depth of D. Every two seconds the submarine can move one unit distance. The ship is equipped with unlimited bombs.
At each second, the ship can do one of the following actions:
-
Move one unit.
-
Release a bomb, and destroy the first submarine vertically under the ship.
-
Do nothing.
At first, the ship’s moving direction is from west to east. It changes its moving direction if and only if the bomb destroys a
special type of submarine.
At no time can submarines overlap at each other.
Every submarine has an important degree. Given the time each submarine enters the sea area at the most west side, and
whether the submarine is the special type, please calculate the maximum sum of destroyed submarines’ important degree in
time [0, S] inclusive.
输入格式
The input consists of multiple test cases. The first line of input contains an integer T, which is the number of test cases.
The input consists of several test cases. Each test case starts with a line containing four integers W, D, N, and S. Each of
the following N lines contains four integers: Gi, Si, Di, Ci. Gi indicates the important degree of i-th submarine; Si is the
time the i-th enters the sea area at the most west side; Di is the submarine’s depth. If Ci is 1 then the submarine is the
special type, otherwise it is a normal one.
[Technical Specification]
T is an integer, and T <= 50.
W, D are integers, and 1 <= W, D <= 3.
N is an integer, and 1 <= N <= 30.
S is an integer, and 1 <= S <= 30.
Gi is an integer, and -1000 <= Gi <= 1000.
Si is an integer, and 0 <= Si <= S,
Di is an integer, and 1 <= Di <= D.
Ci is an integer, and Ci = 0 or 1.
输出格式
For each test case, print a single line containing a number indicating the maximum sum.
样例
Input
2 3 3 4 3 10 1 1 0 10 1 2 0 10 1 3 0 50 3 3 0 3 3 2 3 10 3 1 0 -10 0 1 0
Output
70 10
创建: 15 年，8 月前.
修改: 7 年，2 月前.
最后提交: 3 年，12 月前.
来源: The 4th Baidu Cup Central China Invitational Programming Contest
题目标签