| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 195 | 82 | 45 | 36.885% |
Benson the Rabbit is attending pilot school!
He has $n$ modules to complete, numbered from 1ドル$ to $n$. There are $k$ topics in flying numbered from 1ドル$ to $k$. As Benson is new to flying, he starts with zero knowledge in each topic.
Each of these $n$ modules have a knowledge requirement to complete them. In particular, to complete module $i,ドル Benson requires at least $r[i][j]$ knowledge of topic $j$ for all topics $j$.
Completing a module also allows Benson to gain knowledge in some topics. After completing module $i,ドル he will gain $u[i][j]$ knowledge in topic $j$.
Formally, let Benson’s knowledge in topic $j$ be $p[j]$. Initially, $p[j] = 0$ for all $j$. He can only complete a module $i$ if $p[j] ≥ r[i][j]$ for every topic $j$. After completing module $i,ドル the value of $p[j]$ increases by $u[i][j]$ for each topic $j$.
Benson may complete the modules in any order, but each module may only be completed at most once. Help Benson determine the maximum number of modules he can complete.
The first line of input contains 2ドル$ space-separated integers, $n$ and $k$.
Then, $n$ lines will follow. The $i$-th (1ドル ≤ i ≤ n$) of these lines contains $k$ spaced integers $r[i][1], r[i][2], \dots , r[i][k],ドル denoting the knowledge requirements to complete module $i$.
Another $n$ lines follow. The $i$-th (1ドル ≤ i ≤ n$) of these lines contains $k$ spaced integers $u[i][1], u[i][2], \dots , u[i][k],ドル denoting the knowledge gained after completing module $i$.
The output should contain one integer, the maximum number of modules Benson can complete.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 12 | $n = 1$ |
| 2 | 28 | 1ドル ≤ n, k ≤ 100$ |
| 3 | 21 | $k = 1$ |
| 4 | 39 | No additional restrictions |
3 3 0 0 0 7 9 2 7 8 9 7 8 2 7 7 7 8 10 9
1
Benson can only complete module 1ドル,ドル which has knowledge requirement $[0, 0, 0]$. After which, he gains 7ドル,ドル 8ドル,ドル 2ドル$ knowledge in each of the 3ドル$ topics, but $p = [7, 8, 2]$ is insufficient for him to complete any other module. Since no other sequence allows Benson to complete more than 1ドル$ module, the final answer is 1ドル$.
4 3 5 1 0 0 1 5 0 0 0 7 7 7 0 5 6 1 1 1 8 2 0 8 1 4
4
Benson can complete all 4ドル$ modules in the order 3ドル,ドル 1ドル,ドル 2ドル,ドル 4ドル$.
Since Benson can complete all 4ドル$ modules, the answer is 4ドル$.
5 5 14 11 15 7 15 0 0 0 0 0 9 9 14 2 13 4 3 6 1 0 2 4 7 0 0 5 5 0 0 13 4 4 7 1 0 4 1 0 2 1 2 5 0 2 1 4 0 7 2 12
4
Benson can only complete 4ドル$ modules in the order 2ドル,ドル 4ドル,ドル 5ドル,ドル 3ドル$.
With that, he has knowledge $p = [14, 10, 14, 7, 14]$ which is insufficient to complete any other module. Since no other sequence allows Benson to complete more than 4ドル$ modules, the final answer is 4ドル$.