#P8490. [IOI2022] 鲶鱼塘

[IOI2022] 鲶鱼塘

题目背景

滥用评测资源者封号

由于技术限制,请不要使用 C++ 14 (GCC 9) 提交本题。

这是一道交互题,你只需要实现代码中要求的函数。

你的代码不需要引用任何额外的头文件,也不需要实现 main 函数。

原题时间限制 1s,为了节约评测资源,时间限制修改为 0.5s。

题目描述

Bu Dengklek 有一个鲶鱼塘。这个鲶鱼塘是由 N×NN \times N 个网格单元构成的池塘。每个单元都是相同大小的正方形。网格各列自西向东编号为从 00N1N - 1,各行自南向北编号为从 00N1N - 1。我们把坐落在网格第 cc 列第 rr 行处(0cN10 \le c \le N - 10rN10 \le r \le N - 1)的单元记为单元 (c,r)(c, r)

池塘里总共有 MM 条鲶鱼,编号为从 00M1M - 1,分别位于不同的单元中。对每个满足 0iM10 \le i \le M - 1ii,鲶鱼 ii 在单元 (Xi,Yi)(X_i, Y_i) 中,其重量为 WiW_i 克。

Bu Dengklek 想造些长堤来抓鲶鱼。在第 cc 列中长度为 kk 的长堤(对于所有 0cN10 \le c \le N - 11kN1 \le k \le N),是一个从第 00 行跨到第 k1k - 1 行的矩形,盖住单元 (c,0),(c,1),,(c,k1)(c, 0), (c, 1), \ldots, (c, k - 1)。对于每一列,Bu Dengklek 可以按照她自己选择的某个长度造长堤,也可以不造。

鲶鱼 ii(对所有满足 0iM10 \le i \le M - 1ii)能被抓住,如果有某个长堤紧邻它的西侧或东侧,而且没有长堤盖住它所在的单元;也就是说,如果

  • 单元 (Xi1,Yi)(X_i - 1, Y_i)(Xi+1,Yi)(X_i + 1, Y_i)至少有一个 被某个长堤盖住,而且
  • 没有长堤盖住单元 (Xi,Yi)(X_i, Y_i)

例如,考虑尺寸为 N=5N = 5,有 M=4M = 4 条鲶鱼的池塘:

  • 鲶鱼 00 在单元 (0,2)(0, 2) 中,重量为 55 克。
  • 鲶鱼 11 在单元 (1,1)(1, 1) 中,重量为 22 克。
  • 鲶鱼 22 在单元 (4,4)(4, 4) 中,重量为 11 克。
  • 鲶鱼 33 在单元 (3,3)(3, 3) 中,重量为 33 克。

Bu Dengklek 可以这样来造长堤:

造长堤前 造长堤后

单元中的数字表示该单元中鲶鱼的重量。 阴影单元被长堤盖住。 在该场景中,鲶鱼 00(在单元 (0,2)(0, 2) 中)和鲶鱼 33(在单元 (3,3)(3, 3) 中)能被抓住。 鲶鱼 11(在单元 (1,1)(1, 1) 中)没被抓住,因为有一个长堤盖住了它所在的单元;鲶鱼 22(在单元 (4,4)(4, 4) 中)没被抓住,因为没有长堤紧邻它的西侧或东侧。

Bu Dengklek 希望造出来的长堤能让被抓住的鲶鱼的总重量尽量大。 你的任务是求出 Bu Dengklek 通过造长堤能抓住的鲶鱼的最大总重量。

输入格式

你需要实现下面的函数:

int64 max_weights(int N, int M, int[] X, int[] Y, int[] W)
  • NN:池塘的尺寸。
  • MM:鲶鱼的数量。
  • XX, YY:长度为 MM 的两个数组,给出鲶鱼的位置。
  • WW:长度为 MM 的数组,给出鲶鱼的重量。
  • 该函数需要返回一个整数,表示 Bu Dengklek 通过造长堤能抓住的鲶鱼的最大总重量。
  • 该函数将被恰好调用一次。

输出格式

考虑如下调用:

max_weights(5, 4, [0, 1, 4, 3], [2, 1, 4, 3], [5, 2, 1, 3])

该例子的解释请见前面的题面。

在造完所述的长堤后,Bu Dengklek 能抓住鲶鱼 0033,其总重量为 5+3=85 + 3 = 8 克。 因为无法造出能够抓住总重量超过 88 克的鲶鱼的长堤,函数应当返回 88

提示

约束条件

  • 2N100  0002 \le N \le 100\;000
  • 1M300  0001 \le M \le 300\;000
  • 0XiN10 \le X_i \le N - 10YiN10 \le Y_i \le N - 1(对所有满足 0iM10 \le i \le M - 1ii
  • 1Wi1091 \le W_i \le 10^9(对所有满足 0iM10 \le i \le M - 1ii
  • 任意两条鲶鱼都不会在同一单元中。 换句话说,XiX[j]X_i \neq X[j]YiY[j]Y_i \neq Y[j](对于所有满足 0i<jM10 \le i \lt j \le M - 1iijj)。

子任务

  1. (3 分) XiX_i 是偶数(对于所有满足 0iM10 \le i \le M - 1ii
  2. (6 分) Xi1X_i \le 1(对于所有满足 0iM10 \le i \le M - 1ii
  3. (9 分) Yi=0Y_i = 0(对于所有满足 0iM10 \le i \le M - 1ii
  4. (14 分) N300N \le 300Yi8Y_i \le 8(对于所有满足 0iM10 \le i \le M - 1ii
  5. (21 分) N300N \le 300
  6. (17 分) N3000N \le 3000
  7. (14 分) 在每列中至多有 22 条鲶鱼。
  8. (16 分) 没有额外限制。

评测程序示例

评测程序示例读取如下格式的输入:

  • 11 行:N  MN \; M
  • 2+i2 + i 行(0iM10 \le i \le M - 1):Xi  Yi  WiX_i \; Y_i \; W_i

评测程序示例将按照如下格式打印你的答案:

  • 11 行:max_weights 的返回值

约定

题面在给出函数接口时,会使用一般性的类型名称 voidintint64int[](数组)和 int[][](数组的数组)。

在 C++ 中,评测程序会采用适当的数据类型或实现,如下表所示:

void int int64 int[]
void int long long std::vector<int>
int[][] 数组 a 的长度
std::vector<std::vector<int>> a.size()