题目详情题解（0）讨论（0）提交记录（0）

AT_jsc2019_qual_e.Card Collector

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在一个有 HH 行 WW 列的格子上，总共放置了 NN 张卡片。

第 ii 张卡片上写有整数 AiA_i，并且被放置在从上往下第 RiR_i 行、从左往右第 CiC_i 列的格子上。

同一个格子上可能放有多张卡片。

你可以从每一行中各选取最多 11 张卡片。

接着，你可以从每一列中各选取最多 11 张卡片。

请你求出所选卡片上整数之和的最大值。

输入格式

输入以如下格式从标准输入读入。

NN HH WW R1R_1 C1C_1 A1A_1 R2R_2 C2C_2 A2A_2 ⋮\vdots RNR_N CNC_N ANA_N

输出格式

请输出所选卡片上整数之和的最大值。

输入输出样例

  • 输入#1

    6 2 2
2 2 2
1 1 8
1 1 5
1 2 9
1 2 7
2 1 4

    输出#1

    28

  • 输入#2

    13 5 6
1 3 35902
4 6 19698
4 6 73389
3 6 3031
3 1 4771
1 4 4784
2 1 36357
2 1 24830
5 6 50219
4 6 22645
1 2 30739
1 4 68417
1 5 78537

    输出#2

    430590

  • 输入#3

    1 100000 100000
1 1 1

    输出#3

    1

说明/提示

限制条件

  • 所有输入均为整数。
  • 1≤N≤1051 \leq N \leq 10^5
  • 1≤H,W≤1051 \leq H, W \leq 10^5
  • 1≤Ai≤1051 \leq A_i \leq 10^5
  • 1≤Ri≤H1 \leq R_i \leq H
  • 1≤Ci≤W1 \leq C_i \leq W

样例解释 1

如下选择时，所选卡片上整数之和为 2828，这是最大值。

  • 从第 11 行选取第 44 张卡片。
  • 从第 22 行选取第 66 张卡片。
  • 从第 11 列选取第 22 张卡片。
  • 从第 22 列选取第 55 张卡片。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页