[BalkanOI 2018] Homecoming

Luogu

IDLGP9506

Time500ms

Memory250MB

DifficultyP4

动态规划 DP2018交互题O2优化BalkanOI（巴尔干半岛）

有 $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$。 ## Input 见「交互过程」。 ## Output 见「交互过程」。 [samples] ## Background 翻译自 BalkanOI 2018 Day1 T2「Homecoming」；由于洛谷远慢于 loj，因此将时间限制从 300ms 调整至 500ms。 ## Note ### 数据范围及限制令所有对 `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$ |

API Response (JSON)

{
  "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...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments