luogu#P9506. [BalkanOI2018] Homecoming

[BalkanOI2018] Homecoming

题目背景

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

题目描述

NN 门课程,分别编号为 00N1N-1。如果你 pass 了课程 ii,你可以拿到 AiA _ i 美刀。
NN 本教材,分别编号为 00N1N-1ii 号教材的价格为 BiB _ i 美刀。
如果你要 pass 课程 ii,你需要购买编号为 $i, (i+1) \bmod N, (i+2) \bmod N, \cdots, (i+K-1) \bmod N$ 的课本。KK 为给定的常数。
你的目的是赚钱而非 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])

的返回值为 6060

输入格式

见「交互过程」。

输出格式

见「交互过程」。

提示

数据范围及限制

令所有对 solve 函数的调用中 NN 的总和为 SNS_NNKNK 的总和为 SNKS_{NK}。那么:

  • 1KN2×1061\le K\le N\le 2\times 10^6
  • 1SN2×1061\le S_N\le 2\times 10^6
  • 0Ai,Bi1090\le A_i,B_i\le 10^9

详细子任务及附加限制如下表所示。

子任务编号 附加限制 分值
11 1SN5001\le S_N\le 500 1313
22 1SN50001\le S_N\le 5000 1818
33 1SNK2×1061\le S_{NK}\le 2\times 10^6 3131
44 无附加限制 3838