#PQJ1545x66. QOJ 1545_66
QOJ 1545_66
The 18th Japanese Olympiad in Informatics (JOI 2018/2019) Spring Training Camp/Qualifying Trial March 19–25, 2019 (Komaba/Yoyogi, Tokyo) Contest Day 2 – Two Dishes Two Dishes Cook Bitaro is participating in a cooking contest. In this contest, a contestant is required to cook two dishes: IOI Donburi and JOI Curry. The cooking process of IOI Donburi consists of N steps. The i-th (1 ≤i ≤N) step takes exactly Ai minutes. Initially, he can perform only the first step. To perform the i-th (2 ≤i ≤N) step, he needs to have finished the (i −1)-th step. The cooking process of JOI Curry consists of M steps. The j-th (1 ≤j ≤M) step takes exactly Bj minutes. Initially, he can perform only the first step. To perform the j-th (2 ≤j ≤M) step, he needs to have finished the ( j −1)-th step. The steps need concentration, so if he starts performing a step, he cannot perform other steps until he finishes it. Between steps, he may switch from a dish to the other dish. Once the contest starts, he cannot take a rest until he completes two dishes. By the way, in this contest, a contestant is given artistic scores as follows. • If he finish the i-th (1 ≤i ≤N) step of cooking IOI Donburi within S i minutes from the start of the contest, he is given Pi points. Here, the value of Pi might be negative. • If he finish the j-th (1 ≤j ≤M) step of cooking JOI Curry within T j minutes from the start of the contest, he is given Q j points. Here, the value of Q j might be negative. Bitaro wants to maximize his total artistic scores. Write a program which, given the number of steps of cooking, the time they take, and the information of artistic scores, calculates the maximum total artistic scores Bitaro can gain. Input Read the following data from the standard input. All the values in the input are integers. N M A1 S 1 P1 ... AN S N PN B1 T1 Q1 ... BM TM QM Two Dishes– 1 / 5 The 18th Japanese Olympiad in Informatics (JOI 2018/2019) Spring Training Camp/Qualifying Trial March 19–25, 2019 (Komaba/Yoyogi, Tokyo) Contest Day 2 – Two Dishes Output Write one line to the standard output. The output should contain the maximum total artistic scores Bitaro can gain. Constraints • 1 ≤N ≤1 000 000. • 1 ≤M ≤1 000 000. • 1 ≤Ai ≤1 000 000 000 (1 ≤i ≤N). • 1 ≤Bj ≤1 000 000 000 (1 ≤j ≤M). • 1 ≤S i ≤2 000 000 000 000 000 = 2 × 1015 (1 ≤i ≤N). • 1 ≤T j ≤2 000 000 000 000 000 = 2 × 1015 (1 ≤j ≤M). • −1 000 000 000 ≤Pi ≤1 000 000 000 (1 ≤i ≤N). • −1 000 000 000 ≤Q j ≤1 000 000 000 (1 ≤j ≤M). Subtasks
- (5 points) N ≤200 000, M ≤200 000, S 1 = · · · = S N = T1 = · · · = TM.
- (3 points) N ≤12, M ≤12, Pi = 1 (1 ≤i ≤N), Q j = 1 (1 ≤j ≤M).
- (7 points) N ≤2 000, M ≤2 000, Pi = 1 (1 ≤i ≤N), Q j = 1 (1 ≤j ≤M).
- (39 points) N ≤200 000, M ≤200 000, Pi = 1 (1 ≤i ≤N), Q j = 1 (1 ≤j ≤M).
- (11 points) N ≤200 000, M ≤200 000, 1 ≤Pi (1 ≤i ≤N), 1 ≤Q j (1 ≤j ≤M).
- (9 points) 1 ≤Pi (1 ≤i ≤N), 1 ≤Q j (1 ≤j ≤M).
- (17 points) N ≤200 000, M ≤200 000.
- (9 points) No additional constraints. Two Dishes– 2 / 5 The 18th Japanese Olympiad in Informatics (JOI 2018/2019) Spring Training Camp/Qualifying Trial March 19–25, 2019 (Komaba/Yoyogi, Tokyo) Contest Day 2 – Two Dishes Sample Input and Output Sample Input 1 Sample Output 1 4 3 6 2 1 1 3 8 1 2 13 1 1 13 1 3 6 1 2 11 1 2 15 1 This sample input satisfies the constraints for Subtask 2. In this sample input, Bitaro can perform the steps of cooking as follows, for example:
- He performs the 1st step of JOI Curry. He finishes it 3 minutes after the contest starts. Since this is within 6 minutes, he gains 1 point.
- He performs the 1st step of IOI Donburi. He finishes it 5 minutes after the contest starts. Since this is not within 1 minute, he gains no artistic scores.
- He performs the 2nd step of IOI Donburi. He finishes it 8 minutes after the contest starts. Since this is within 8 minutes, he gains 1 point.
- He performs the 2nd step of JOI Curry. He finishes it 10 minutes after the contest starts. Since this is within 11 minutes, he gains 1 point.
- He performs the 3rd step of IOI Donburi. He finishes it 12 minutes after the contest starts. Since this is within 13 minutes, he gains 1 point.
- He performs the 4th step of IOI Donburi. He finishes it 13 minutes after the contest starts. Since this is within 13 minutes, he gains 1 point.
- He performs the 3rd step of JOI Curry. He finishes it 15 minutes after the contest starts. Since this is within 15 minutes, he gains 1 point. Here the total artistic scores are 6 points. He cannot gain more than 6 points, so output 6. Two Dishes– 3 / 5 The 18th Japanese Olympiad in Informatics (JOI 2018/2019) Spring Training Camp/Qualifying Trial March 19–25, 2019 (Komaba/Yoyogi, Tokyo) Contest Day 2 – Two Dishes Sample Input 2 Sample Output 2 5 7 63 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 This sample input satisfies the constraints for Subtask 1. Two Dishes– 4 / 5 The 18th Japanese Olympiad in Informatics (JOI 2018/2019) Spring Training Camp/Qualifying Trial March 19–25, 2019 (Komaba/Yoyogi, Tokyo) Contest Day 2 – Two Dishes Sample Input 3 Sample Output 3 9 11 99 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 Two Dishes– 5 / 5