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

AT_arc056_d.[ARC056D] サケノミ

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

你来到了一个与众不同的酒吧。在这个酒吧里，有 NN 种饮品，你一开始会得到 NN 个玻璃杯。第 ii 个玻璃杯对应第 ii 种饮品，只能倒入第 ii 种饮品。每种饮品都有一个确定的美味度 wiw_i。一开始，所有玻璃杯都是空的。

每种饮品会在若干个特定时刻被补充。也就是说，在时间 ti,j (1≤j≤Mi)t_{i,j}\ (1 \leq j \leq M_i) 时，如果第 ii 个玻璃杯是空的，就会倒入第 ii 种饮品。

你可以在任意奇数时刻，将所有玻璃杯中的饮品全部喝光。禁止只喝部分饮品。每次喝下的饮品的美味度会累加到总和中。需要注意的是，即使多次喝到同一种饮品，其美味度也会重复计算。

请编写程序，求出可以获得的美味度总和的最大值。

输入格式

输入通过标准输入给出，格式如下：

NN w1w_1 ... wNw_N M1M_1 t1,1t_{1,1} ... t1,M1t_{1,M_1} : MNM_N tN,1t_{N,1} ... tN,MNt_{N,M_N}

输出格式

输出一行，表示美味度总和的最大值。

输入输出样例

  • 输入#1

    3
2 5 -6
1 2
2 4 10
2 4 8

    输出#1

    6

  • 输入#2

    3
2 5 -6
2 2 8
2 4 10
2 4 10

    输出#2

    3

  • 输入#3

    3
3 5 -4
2 2 8
4 4 6 10 12
4 2 4 8 10

    输出#3

    18

  • 输入#4

    3
-2 -2 -2
2 2 8
4 4 6 10 12
4 2 4 8 10

    输出#4

    0

说明/提示

限制条件

  • 1≤N≤5×1051 \leq N \leq 5 \times 10^5
  • 2≤ti,j≤1062 \leq t_{i,j} \leq 10^6
  • ti,j<ti,j+1t_{i,j} < t_{i,j+1}
  • ti,jt_{i,j} 是偶数
  • ∑Mi≤5×105\sum M_i \leq 5 \times 10^5
  • 1≤Mi1 \leq M_i
  • −109≤wi≤109-10^9 \leq w_i \leq 10^9

部分得分

  • 若所有测试用例满足 ti,j≤1,000t_{i,j} \leq 1,000 且 N≤1,000N \leq 1,000，则可获得部分分 3030 分。

样例说明 1

在时刻 99 和 1111 将所有玻璃杯中的饮品喝光。时刻 99 时，3 种饮品都已倒入，因此获得美味度 2+5−6=12+5-6=1。时刻 1111 时，只有第 2 种饮品被倒入，因此获得美味度 55。总共获得 66。

由 ChatGPT 4.1 翻译

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

首页