17672번 - 두 요리 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1024 MB | 142 | 40 | 25 | 23.810% |
문제
요리사 비타로는 요리 대회에 참여했다. 이 대회에서 참가자는 IOI 돈부리와 JOI 카레를 요리해야 한다.
IOI 돈부리를 요리하는 방법은 $N$단계로 이루어져 있다. $i$ 번째 ($1 \le i \le N$) 단계는 정확히 $A_i$분이 걸린다. 처음에, 그는 첫 번째 단계만 실행할 수 있다. $i$번째 ($2 \le i \le N$) 단계를 실행하려면, $(i-1)$번째 단계를 끝마쳐야 한다.
JOI 카레를 요리하는 방법은 $M$단계로 이루어져 있다. $j$ 번째 ($1 \le j \le M$) 단계는 정확히 $B_j$분이 걸린다. 처음에, 그는 첫 번째 단계만 실행할 수 있다. $j$번째 ($2 \le j \le M$) 단계를 실행하려면, $(j-1)$번째 단계를 끝마쳐야 한다.
각 단계를 집중해야 하기 때문에, 한 단계를 시작하면, 그 단계를 끝날 때 까지 다른 단계를 실행할 수 없다. 한 단계가 끝난 이후에는 다른 요리의 단계를 시작해도 상관 없다. 대회가 시작하면 두 요리가 끝나기 까지의 쉬는 시간은 없다.
이 대회에서는, 각 참가자는 예술 점수를 다음 기준에 따라 받는다.
- IOI 돈부리를 만드는 $i$번째 ($1 \le i \le N$) 단계를 처음부터 $S_i$분 안에 끝냈을 경우 $P_i$점을 얻는다. $P_i$는 음수 일 수도 있다.
- JOI 카레를 만드는 $j$번째 ($1 \le j \le M$) 단계를 처음부터 $T_j$분 안에 끝냈을 경우 $Q_j$점을 얻는다. $Q_j$는 음수 일 수도 있다.
비타로는 예술 점수를 최대화 하고 싶다.
요리 단계의 수와, 각 단계에 걸리는 시간과, 예술 점수의 정보가 주어졌을 때, 비타로가 얻을 수 있는 예술 점수의 최댓값을 구하여라.
입력
표준 입력에서 다음과 같은 형식으로 주어진다. 모든 값은 정수이다.
$N$ $M$
$A_1$ $S_1$ $P_1$
$\vdots$
$A_N$ $S_N$ $P_N$ $B_1$ $T_1$ $Q_1$
$\vdots$
$B_M$ $T_M$ $Q_M$
출력
표준 출력으로 한 개의 줄을 출력하여라. 이는 비타로가 얻을 수 있는 예술 점수의 최댓값이다.
제한
- $1 \le N \le 1\ 000\ 000$.
- $1 \le M \le 1\ 000\ 000$.
- $1 \le A_i \le 1\ 000\ 000\ 000$ ($1 \le i \le N$).
- $1 \le B_j \le 1\ 000\ 000\ 000$ ($1 \le j \le M$).
- $1 \le S_i \le 2\ 000\ 000\ 000\ 000\ 000 = 2 \times 10^{15}$ ($1 \le i \le N$).
- $1 \le T_j \le 2\ 000\ 000\ 000\ 000\ 000 = 2 \times 10^{15}$ ($1 \le j \le M$).
- $-1\ 000\ 000\ 000 \le P_i \le 1\ 000\ 000\ 000$ ($1 \le i \le N$).
- $-1\ 000\ 000\ 000 \le Q_j \le 1\ 000\ 000\ 000$ ($1 \le j \le M$).
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | N ≤ 200 000, M ≤ 200 000, S1 = · · · = SN = T1 = · · · = TM. |
| 2 | 3 | N ≤ 12, M ≤ 12, Pi = 1 (1 ≤ i ≤ N), Qj = 1 (1 ≤ j ≤ M). |
| 3 | 7 | N ≤ 2 000, M ≤ 2 000, Pi = 1 (1 ≤ i ≤ N), Qj = 1 (1 ≤ j ≤ M). |
| 4 | 39 | N ≤ 200 000, M ≤ 200 000, Pi = 1 (1 ≤ i ≤ N), Qj = 1 (1 ≤ j ≤ M). |
| 5 | 11 | N ≤ 200 000, M ≤ 200 000, 1 ≤ Pi (1 ≤ i ≤ N), 1 ≤ Qj (1 ≤ j ≤ M). |
| 6 | 9 | 1 ≤ Pi (1 ≤ i ≤ N), 1 ≤ Qj (1 ≤ j ≤ M). |
| 7 | 17 | N ≤ 200 000, M ≤ 200 000. |
| 8 | 9 | No additional constraints. |
예제 입력 1
4 3 2 1 1 3 8 1 2 13 1 1 13 1 3 6 1 2 11 1 2 15 1
예제 출력 1
6
이 입력에서 비타로는 다음과 같은 방식으로 요리 할 수 있다.
- JOI 돈부리의 첫 번째 단계를 요리한다. 그는 대회가 시작한 후 3분 후에 단계를 끝낸다. 6분 안이므로, 1점을 얻는다.
- IOI 카레의 첫 번째 단계를 요리한다. 그는 대회가 시작한 후 5분 후에 단계를 끝낸다. 1분 밖이므로, 아무 점수도 얻지 못한다.
- IOI 돈부리의 두 번째 단계를 요리한다. 그는 대회가 시작한 후 8분 후에 단계를 끝낸다. 8분 안이므로, 1점을 얻는다.
- JOI 카레의 두 번째 단계를 요리한다. 그는 대회가 시작한 후 10분 후에 단계를 끝낸다. 11분 안이므로, 1점을 얻는다.
- IOI 돈부리의 세 번째 단계를 요리한다. 그는 대회가 시작한 후 12분 후에 단계를 끝낸다. 13분 안이므로, 1점을 얻는다.
- IOI 돈부리의 네 번째 단계를 요리한다. 그는 대회가 시작한 후 13분 후에 단계를 끝낸다. 13분 안이므로, 1점을 얻는다.
- JOI 커리의 세 번째 단계를 요리한다. 그는 대회가 시작한 후 15분 후에 단계를 끝낸다. 15분 안이므로, 1점을 얻는다.
총 예술점수는 6점이다. 6점 보다 더 많은 점수를 얻을 수는 없으므로 6을 출력해야 한다.
예제 입력 2
5 7 16 73 16 17 73 10 20 73 1 14 73 16 18 73 10 3 73 2 10 73 7 16 73 19 12 73 4 15 73 15 20 73 14 15 73 8
예제 출력 2
63
예제 입력 3
9 11 86 565 58 41 469 -95 73 679 28 91 585 -78 17 513 -63 48 878 -66 66 901 59 72 983 -70 68 1432 11 42 386 -87 36 895 57 100 164 10 96 812 -6 23 961 -66 54 193 51 37 709 82 62 148 -36 28 853 22 15 44 53 77 660 -19
예제 출력 3
99
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호