P9506 [BalkanOI 2018] Homecoming

翻译自 BalkanOI 2018 Day1 T2「Homecoming」；由于洛谷远慢于 loj，因此将时间限制从 300ms 调整至 500ms。

有 $N$ 门课程，分别编号为 $0$ 到 $N-1$。如果你 pass 了课程 $i$，你可以拿到 $A _ i$ 美刀。 有 $N$ 本教材，分别编号为 $0$ 到 $N-1$。$i$ 号教材的价格为 $B _ i$ 美刀。 如果你要 pass 课程 $i$，你需要购买编号为 $i, (i+1) \bmod N, (i+2) \bmod N, \cdots, (i+K-1) \bmod N$ 的课本。$K$ 为给定的常数。 你的目的是赚钱而非 pass 所有课程。请求出你最多能赚多少美刀。 ## 交互过程 本题只支持 C++ 语言使用函数交互测评。**选手代码不需要也不能包含 `homecoming.h`，也不需要实现 `main` 函数。** 选手程序需要实现如下函数： ``` long long int solve(int N, int K, int *A, int *B); ``` 在一次运行中这个函数可能会被调用多次。 ## 样例 调用 ``` solve(3, 2, [40, 80, 100], [140, 0, 20]) ``` 的返回值为 $60$。

见「交互过程」。

见「交互过程」。

### 数据范围及限制 令所有对 `solve` 函数的调用中 $N$ 的总和为 $S_N$，$NK$ 的总和为 $S_{NK}$。那么： - $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$ 详细子任务及附加限制如下表所示。 | 子任务编号 | 附加限制 | 分值 | | :-----------: | :-----------: | :-----------: | | $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$ | 无附加限制 | $38$ |