4564 . 貳零貳參建北電資演算法小社賽 pD - Dynamic Programming
TopCoder
Tags
Description
恭喜上禮拜很多人都打過了大社賽了
如果沒聽過subtask請參閱小社賽規則
現在你這位電神正在參加建北電資小社賽，因為你目前還沒破台，所以你現在要準備喇分以免這題AC不了，其中，評估各個subtask的效益非常重要，因為你必須在有限時間中得到最高的分數，如果你有仔細看題目的話，你會看到每一題的subtask，以及分數
請先去看 大社賽pE 的題目及subtask
你會發現，第一個subtask" $ m = 0 $ "非常簡單，你只要輸出0你就會拿到這個subtask的$1$分，畢竟$807$會依據題目的難度來出題，相信輸出0大家都會，而且也能在$30$秒內寫完，這顯然非常重要，因為可以讓你從第二變第一@cot。
這次資訊競賽有$n$題，每題有$a _ i$個subtask，每個subtask的分數為$v _ {ij}$，而且每題AC的分數都是100，且最後一筆測資必為無其他限制(須通過最後一筆測資才會AC)。
你目前只剩下$T$秒已經解出了第$i$題的$c _ i$個subtask，分別是$b _ {ix}$
現在你對於第$i$題有$k _ i$種想法，從中選擇一個來做，每種想法，你能預估你花$t _ {iy}$時間能寫出來，你會通過$s _ {iy}$個subtask，分別是通過通過的subtask編號$u _ {iyz}$
如此一來，你能預估你最多能得到多少分。
Input Format
$n$ $T$
$a _ 1$ $v _ {11}$ $v _ {1j}$ ... $v _ {1a _ 1}$
$a _ i$ $v _ {i1}$ $v _ {ij}$ ... $v _ {ia _ i}$
...
$a _ n$ $v _ {n1}$ $v _ {nj}$ ... $v _ {na _ i}$
$c _ 1$ $b _ {11}$ $b _ {1x}$ ... $b _ {1c _ 1}$
$c _ i$ $b _ {i1}$ $b _ {ix}$ ... $b _ {ic _ i}$
...
$c _ n$ $b _ {n1}$ $b _ {nx}$ ... $b _ {nc _ n}$
$k _ i$
$s _ {i1}$ $t _ {i1}$ $u _ {i11}$ $u _ {i1z}$ ... $u _ {i1(s _ {i1})}$
$s _ {iy}$ $t _ {iy}$ $u _ {iy1}$ $u _ {iyz}$ ... $u _ {iy(s _ {iy})}$
...
$s _ {ik _ i}$ $t _ {ik _ i}$ $u _ {ik _ i1}$ $u _ {ik _ iz}$ ... $u _ {ik _ i(s _ {ik _ i})}$
...
當中$n$代表有多少題目，$T$代表有剩餘多少時間
$a$代表該題有多少subtask，$u$代表subtask的分數
$c$代表已經多少筆subtask通過，$b$代表通過測資邊號
$k$代表該題有多少解法，$s$代表有多少筆可以過，$t$代表所需時間，$u$代表會通過的subtask編號
(編號皆為0base)
$0 \le n \le 100$
$0 \le T \le 10 ^ 5$
$0 \le k \le 100$
$1 \le a \le 10$
$0 \le t \le 10 ^ 5$
$0 \le b _ {ix} \lt a _ i$
$0 \le u _ {iyz} \lt a _ i$
$0 \le s _ i \lt a _ i$
$0 \le c _ i \lt a _ i$
Output Format
輸出一個非負整數，代表最高可能得分
Sample Input 1
8 10 6 13 22 8 3 19 19
4 54 14 4 28
4 37 4 17 42
1 100
5 45 3 22 18 12
6 11 21 5 27 15 21
3 5 1 3
2 0 1
2 1 0
0
1 1
2 0 3
2
5 72 5 1 4 0 3
7 410 6 5 4 2 1 3 0
0
2
3 7 0 2 1
3 22 2 1 0
0
3
4 517 1 3 0 2
4 680 1 0 3 2
2 61 3 0
1
3 263 4 3 2
Sample Output 1
Sample Input 2
Sample Output 2
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~4 | $k _ i = 0$ | 1 |
| 2 | 5~9 | $a _ i = c _ i$ | 1 |
| 3 | 10~14 | $n = 1 $ 且 $ k _ i = 1$ | 2 |
| 4 | 15~19 | $t _ i = 0$ | 3 |
| 5 | 20~24 | $c _ i = 0$ | 5 |
| 6 | 25~29 | $a _ i = 1$ | 8 |
| 7 | 30~39 | $k _ i = 1$ | 13 |
| 8 | 40~49 | $n = 1$ | 21 |
| 9 | 50~69 | no other limits | 46 |