IOI 2022 Day 1 Task1

2023-10-20 12:10

文章标签 day 2022 task1 ioi

本文主要是介绍IOI 2022 Day 1 Task1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Task 1

鲶⻥塘（fish）
Bu Dengklek 有⼀个鲶⻥塘。这个鲶⻥塘是由 N × N 个⽹格单元构成的池塘。每个单元都是相同⼤⼩的正⽅形。⽹格各列⾃西向东编号为从 0 到 N − 1，各⾏⾃南向北编号为从 0 到 N − 1。我们把坐落在⽹格第 c 列第 r ⾏处（0 ≤ c ≤ N − 1，0 ≤ r ≤ N − 1）的单元记为单元 (c, r)。池塘⾥总共有 M 条鲶⻥，编号为从 0 到 M − 1，分别位于不同的单元中。对每个满⾜ 0 ≤ i ≤ M − 1 的 i，鲶⻥ i 在单元 (X[i],Y [i]) 中，其重量为 W[i] 克。 Bu Dengklek 想造些⻓堤来抓鲶⻥。在第 c 列中⻓度为 k 的⻓堤（对于所有 0 ≤ c ≤ N − 1 和 1 ≤ k ≤ N），是⼀个从第 0 ⾏跨到第 k − 1 ⾏的矩形，盖住单元 (c, 0),(c, 1),…,(c, k − 1)。对于每⼀列，Bu Dengklek 可以按照她⾃⼰选择的某个⻓度造⻓堤，也可以不造。鲶⻥ i （对所有满⾜ 0 ≤ i ≤ M − 1 的 i）能被抓住，如果有某个⻓堤紧邻它的西侧或东侧，⽽且没有⻓堤盖住它所在的单元；也就是说，如果单元 (X[i] − 1,Y [i]) 或 (X[i] + 1,Y [i]) 中⾄少有⼀个被某个⻓堤盖住，⽽且没有⻓堤盖住单元 (X[i],Y [i])。例如，考虑尺⼨为 N = 5，有 M = 4 条鲶⻥的池塘：鲶⻥ 0 在单元 (0, 2) 中，重量为 5 克。鲶⻥ 1 在单元 (1, 1) 中，重量为 2 克。鲶⻥ 2 在单元 (4, 4) 中，重量为 1 克。鲶⻥ 3 在单元 (3, 3) 中，重量为 3 克。 Bu Dengklek 可以这样来造⻓堤：
在这里插入图片描述
单元中的数字表⽰该单元中鲶⻥的重量。阴影单元被⻓堤盖住。在该场景中，鲶⻥ 0（在单元 (0, 2) 中）和鲶⻥ 3（在单元 (3, 3) 中）能被抓住。鲶⻥ 1（在单元 (1, 1) 中）没被抓住，因为有⼀个⻓堤盖住了它所在的单元；鲶⻥ 2（在单元 (4, 4) 中）没被抓住，因为没有⻓堤紧邻它的西侧或东侧。 Bu Dengklek 希望造出来的⻓堤能让被抓住的鲶⻥的总重量尽量⼤。你的任务是求出 Bu Dengklek 通
过造⻓堤能抓住的鲶⻥的最⼤总重量。实现细节你需要实现下⾯的函数：

int64 max_weights(int N, int M, int[] X, int[] Y, int[] W)

N：池塘的尺⼨。
M：鲶⻥的数量。
X, Y ：⻓度为 M 的两个数组，给出鲶⻥的位置。
W：⻓度为 M 的数组，给出鲶⻥的重量。该函数需要返回⼀个整数，表⽰ Bu Dengklek 通过造⻓堤能抓住的鲶⻥的最⼤总重量。该函数将被恰好调⽤⼀次。

例⼦

考虑如下调⽤：

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

该例⼦的解释请⻅前⾯的题⾯。
在造完所述的⻓堤后，Bu Dengklek 能抓住鲶⻥ 0 和 3，其总重量为 5 + 3 = 8 克。因为⽆法造出能够抓住总重量超过 8 克的鲶⻥的⻓堤，函数应当返回 8。

约束条件

2 ≤ N ≤ 100 000
1 ≤ M ≤ 300 000
0 ≤ X[i] ≤ N − 1，0 ≤ Y [i] ≤ N − 1（对所有满⾜ 0 ≤ i ≤ M − 1 的 i）
1 ≤ W[i] ≤ 109（对所有满⾜ 0 ≤ i ≤ M − 1 的 i）
任意两条鲶⻥都不会在同⼀单元中。换句话说，X[i] ≠ X[j] 或 Y [i] ≠ Y [j]（对于所有满⾜ 0 ≤ i < j ≤ M − 1 的 i 和 j）。