P9506 [BalkanOI 2018] Homecoming

Translated from BalkanOI 2018 Day 1 T2 “Homecoming”. Since Luogu is much slower than loj, the time limit is adjusted from 300 ms to 500 ms.

There are $N$ courses, numbered from $0$ to $N-1$. If you pass course $i$, you can earn $A_i$ dollars. There are $N$ textbooks, numbered from $0$ to $N-1$. The price of textbook $i$ is $B_i$ dollars. If you want to pass course $i$, you need to buy the textbooks numbered $i, (i+1) \bmod N, (i+2) \bmod N, \cdots, (i+K-1) \bmod N$. $K$ is a given constant. Your goal is to make money rather than pass all courses. Please compute the maximum number of dollars you can earn.

See “Interaction”.

See “Interaction”.

### Constraints and Limits Let the sum of $N$ over all calls to the `solve` function be $S_N$, and the sum of $NK$ be $S_{NK}$. Then: - $1\le K\le N\le 2\times 10^6$ - $1\le S_N\le 2\times 10^6$ - $0\le A_i,B_i\le 10^9$ The detailed subtasks and additional limits are shown in the table below. | Subtask ID | Additional Limits | Score | | :-----------: | :-----------: | :-----------: | | $1$ | $1\le S_N\le 500$ | $13$ | | $2$ | $1\le S_N\le 5000$ | $18$ | | $3$ | $1\le S_{NK}\le 2\times 10^6$ | $31$ | | $4$ | No additional limits | $38$ | Translated by ChatGPT 5