28495번 - Topical 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 207 | 85 | 48 | 37.795% |
문제
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 ≤ n, k ≤ 10^6$
- $n \cdot k ≤ 10^6$
- $0 ≤ u[i][j], r[i][j] ≤ 10^9$ (for all $1 ≤ i ≤ n$ and $1 ≤ j ≤ k$).
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 12 | $n = 1$ |
| 2 | 28 | $1 ≤ n, k ≤ 100$ |
| 3 | 21 | $k = 1$ |
| 4 | 39 | No additional restrictions |
예제 입력 1
3 3 0 0 0 7 9 2 7 8 9 7 8 2 7 7 7 8 10 9
예제 출력 1
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$.
예제 입력 2
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
예제 출력 2
4
Benson can complete all $4$ modules in the order $3$, $1$, $2$, $4$.
- With initial knowledge $p = [0, 0, 0]$, he can complete module $3$ and his knowledge increases by $u[3] = [8, 2, 0]$.
- With knowledge $p = [8, 2, 0]$, he can complete module $1$ and his knowledge increases by $u[1] = [0, 5, 6]$.
- With knowledge $p = [8, 7, 6]$, he can complete module $2$ and his knowledge increases by $u[2] = [1, 1, 1]$.
- With knowledge $p = [9, 8, 7]$, he can complete module $4$ and his knowledge increases by $u[4] = [8, 1, 4]$.
Since Benson can complete all $4$ modules, the answer is $4$.
예제 입력 3
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
예제 출력 3
4
Benson can only complete $4$ modules in the order $2$, $4$, $5$, $3$.
- With initial knowledge $p = [0, 0, 0, 0, 0]$, he can complete module $2$ and his knowledge increases by $u[2] = [4, 4, 7, 1, 0]$.
- With knowledge $p = [4, 4, 7, 1, 0]$, he can complete module $4$ and his knowledge increases by $u[4] = [2, 5, 0, 2, 1].
- With knowledge $p = [6, 9, 7, 3, 1]$, he can complete module $5$ and his knowledge increases by $u[5] = [4, 0, 7, 2, 12]$.
- With knowledge $p = [10, 9, 14, 5, 13]$, he can complete module $3$ and his knowledge increases by $u[4] = [4, 1, 0, 2, 1]$.
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$.
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호