{"problem":{"name":"[BalkanOI 2018] Homecoming","description":{"content":"有 $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","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":500,"memory_limit":256000},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9506"},"statements":[{"statement_type":"Markdown","content":"有 $N$ 门课程，分别编号为 $0$ 到 $N-1$。如果你 pass 了课程 $i$，你可以拿到 $A _ i$ 美刀。  \n有 $N$ 本教材，分别编号为 $0$ 到 $N-1$。$i$ 号教材的价格为 $B _ i$ 美刀。  \n如果你要 pass 课程 $i$，你需要购买编号为 $i, (i+1) \\bmod N, (i+2) \\bmod N, \\cdots, (i+K-1) \\bmod N$ 的课本。$K$ 为给定的常数。  \n你的目的是赚钱而非 pass 所有课程。请求出你最多能赚多少美刀。\n\n## 交互过程\n\n本题只支持 C++ 语言使用函数交互测评。**选手代码不需要也不能包含 `homecoming.h`，也不需要实现 `main` 函数。**\n\n选手程序需要实现如下函数：\n\n```\nlong long int solve(int N, int K, int *A, int *B);\n```\n\n在一次运行中这个函数可能会被调用多次。\n\n## 样例\n\n调用\n\n```\nsolve(3, 2,\n[40, 80, 100],\n[140, 0, 20])\n```\n\n的返回值为 $60$。\n\n## Input\n\n见「交互过程」。\n\n## Output\n\n见「交互过程」。\n\n[samples]\n\n## Background\n\n翻译自 BalkanOI 2018 Day1 T2「Homecoming」；由于洛谷远慢于 loj，因此将时间限制从 300ms 调整至 500ms。\n\n## Note\n\n### 数据范围及限制\n\n令所有对 `solve` 函数的调用中 $N$ 的总和为 $S_N$，$NK$ 的总和为 $S_{NK}$。那么：\n\n- $1\\le K\\le N\\le 2\\times 10^6$\n- $1\\le S_N\\le 2\\times 10^6$\n- $0\\le A_i,B_i\\le 10^9$\n\n详细子任务及附加限制如下表所示。\n\n| 子任务编号 | 附加限制 | 分值 |\n| :-----------: | :-----------: | :-----------: |\n| $1$ | $1\\le S_N\\le 500$ | $13$ |\n| $2$ | $1\\le S_N\\le 5000$ | $18$ |\n| $3$ | $1\\le S_{NK}\\le 2\\times 10^6$ | $31$ |\n| $4$ | 无附加限制 | $38$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9506","tags":["动态规划 DP","2018","交互题","O2优化","BalkanOI（巴尔干半岛）"],"sample_group":[],"created_at":"2026-03-03 11:09:25"}}