{"problem":{"name":"[IOI 2022] 鲶鱼塘","description":{"content":"Bu Dengklek 有一个鲶鱼塘。这个鲶鱼塘是由 $N \\times N$ 个网格单元构成的池塘。每个单元都是相同大小的正方形。网格各列自西向东编号为从 $0$ 到 $N - 1$，各行自南向北编号为从 $0$ 到 $N - 1$。我们把坐落在网格第 $c$ 列第 $r$ 行处（$0 \\le c \\le N - 1$，$0 \\le r \\le N - 1$）的单元记为单元 $(c, r)$。 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":2097152},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8490"},"statements":[{"statement_type":"Markdown","content":"Bu Dengklek 有一个鲶鱼塘。这个鲶鱼塘是由 $N \\times N$ 个网格单元构成的池塘。每个单元都是相同大小的正方形。网格各列自西向东编号为从 $0$ 到 $N - 1$，各行自南向北编号为从 $0$ 到 $N - 1$。我们把坐落在网格第 $c$ 列第 $r$ 行处（$0 \\le c \\le N - 1$，$0 \\le r \\le N - 1$）的单元记为单元 $(c, r)$。\n\n池塘里总共有 $M$ 条鲶鱼，编号为从 $0$ 到 $M - 1$，分别位于**不同的**单元中。对每个满足 $0 \\le i \\le M - 1$ 的 $i$，鲶鱼 $i$ 在单元 $(X_i, Y_i)$ 中，其重量为 $W_i$ 克。\n\nBu Dengklek 想造些长堤来抓鲶鱼。在第 $c$ 列中长度为 $k$ 的长堤（对于所有 $0 \\le c \\le N - 1$ 和 $1 \\le k \\le N$），是一个从第 $0$ 行跨到第 $k - 1$ 行的矩形，盖住单元 $(c, 0), (c, 1), \\ldots, (c, k - 1)$。对于每一列，Bu Dengklek 可以按照她自己选择的某个长度造长堤，也可以不造。\n\n鲶鱼 $i$（对所有满足 $0 \\le i \\le M - 1$ 的 $i$）能被抓住，如果有某个长堤紧邻它的西侧或东侧，而且没有长堤盖住它所在的单元；也就是说，如果\n* 单元 $(X_i - 1, Y_i)$ 或 $(X_i + 1, Y_i)$ 中 **至少有一个** 被某个长堤盖住，而且\n* 没有长堤盖住单元 $(X_i, Y_i)$。\n\n例如，考虑尺寸为 $N = 5$，有 $M = 4$ 条鲶鱼的池塘：\n\n* 鲶鱼 $0$ 在单元 $(0, 2)$ 中，重量为 $5$ 克。\n* 鲶鱼 $1$ 在单元 $(1, 1)$ 中，重量为 $2$ 克。\n* 鲶鱼 $2$ 在单元 $(4, 4)$ 中，重量为 $1$ 克。\n* 鲶鱼 $3$ 在单元 $(3, 3)$ 中，重量为 $3$ 克。\n\nBu Dengklek 可以这样来造长堤：\n\n| 造长堤前 | 造长堤后 |\n| :---: | :---: |\n| ![](https://cdn.luogu.com.cn/upload/image_hosting/2rcnqc7k.png) | ![](https://cdn.luogu.com.cn/upload/image_hosting/yesaiovt.png) |\n\n单元中的数字表示该单元中鲶鱼的重量。\n阴影单元被长堤盖住。\n在该场景中，鲶鱼 $0$（在单元 $(0, 2)$ 中）和鲶鱼 $3$（在单元 $(3, 3)$ 中）能被抓住。\n鲶鱼 $1$（在单元 $(1, 1)$ 中）没被抓住，因为有一个长堤盖住了它所在的单元；鲶鱼 $2$（在单元 $(4, 4)$ 中）没被抓住，因为没有长堤紧邻它的西侧或东侧。\n\nBu Dengklek 希望造出来的长堤能让被抓住的鲶鱼的总重量尽量大。\n你的任务是求出 Bu Dengklek 通过造长堤能抓住的鲶鱼的最大总重量。\n\n## Input\n\n你需要实现下面的函数：\n\n```go\nint64 max_weights(int N, int M, int[] X, int[] Y, int[] W)\n```\n\n* $N$：池塘的尺寸。\n* $M$：鲶鱼的数量。\n* $X$, $Y$：长度为 $M$ 的两个数组，给出鲶鱼的位置。\n* $W$：长度为 $M$ 的数组，给出鲶鱼的重量。\n* 该函数需要返回一个整数，表示 Bu Dengklek 通过造长堤能抓住的鲶鱼的最大总重量。\n* 该函数将被恰好调用一次。\n\n## Output\n\n考虑如下调用：\n\n```go\nmax_weights(5, 4, [0, 1, 4, 3], [2, 1, 4, 3], [5, 2, 1, 3])\n```\n\n该例子的解释请见前面的题面。\n\n在造完所述的长堤后，Bu Dengklek 能抓住鲶鱼 $0$ 和 $3$，其总重量为 $5 + 3 = 8$ 克。\n因为无法造出能够抓住总重量超过  $8$ 克的鲶鱼的长堤，函数应当返回 $8$。\n\n[samples]\n\n## Background\n\n### 由于技术限制，请不要使用 C++ 14 (GCC 9) 提交本题。\n\n这是一道交互题，你只需要实现代码中要求的函数。\n\n你的代码不需要引用任何额外的头文件，也不需要实现 main 函数。\n\n## Note\n\n### 约束条件\n\n* $2 \\le N \\le 100\\;000$\n* $1 \\le M \\le 300\\;000$\n* $0 \\le X_i \\le N - 1$，$0 \\le Y_i \\le N - 1$（对所有满足 $0 \\le i \\le M - 1$ 的 $i$）\n* $1 \\le W_i \\le 10^9$（对所有满足 $0 \\le i \\le M - 1$ 的 $i$）\n* 任意两条鲶鱼都不会在同一单元中。\n  换句话说，$X_i \\neq X[j]$ 或 $Y_i \\neq Y[j]$（对于所有满足 $0 \\le i \\lt j \\le M - 1$ 的 $i$ 和 $j$）。\n\n### 子任务\n\n1. （3 分） $X_i$ 是偶数（对于所有满足 $0 \\le i \\le M - 1$ 的 $i$）\n1. （6 分） $X_i \\le 1$（对于所有满足 $0 \\le i \\le M - 1$ 的 $i$）\n1. （9 分） $Y_i = 0$（对于所有满足 $0 \\le i \\le M - 1$ 的 $i$）\n1. （14 分） $N \\le 300$，$Y_i \\le 8$（对于所有满足 $0 \\le i \\le M - 1$ 的 $i$）\n1. （21 分） $N \\le 300$\n1. （17 分） $N \\le 3000$\n1. （14 分） 在每列中至多有 $2$ 条鲶鱼。\n1. （16 分） 没有额外限制。\n\n### 评测程序示例\n\n评测程序示例读取如下格式的输入：\n\n* 第 $1$ 行：$N \\; M$\n* 第 $2 + i$ 行（$0 \\le i \\le M - 1$）：$X_i \\; Y_i \\; W_i$\n\n评测程序示例将按照如下格式打印你的答案：\n\n* 第 $1$ 行：`max_weights` 的返回值\n\n### 约定\n\n题面在给出函数接口时，会使用一般性的类型名称 `void`、`int`、`int64`、`int[]`（数组）和 `int[][]`（数组的数组）。\n\n在 C++ 中，评测程序会采用适当的数据类型或实现，如下表所示：\n\n| `void ` | `int` | `int64`     | `int[]`            |\n| ------- | ----- | ----------- | ------------------ |\n| `void ` | `int` | `long long` | `std::vector<int>` |\n\n| `int[][]`                       | 数组 `a` 的长度 |\n| ------------------------------- | ------------------- |\n| `std::vector<std::vector<int>>` | `a.size()`          |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8490","tags":["动态规划 DP","2022","IOI","交互题","动态规划优化","前缀和","Ad-hoc"],"sample_group":[],"created_at":"2026-03-03 11:09:25"}}