← 返回题目列表

AtCoder · ndpc2026_o

O. 游戏

中文机器翻译题面 查看原题

分数: 7 点

问题陈述

你要玩一个游戏。游戏由以下动作组成 N 天。每天,您选择一个整数 x \in {0,1,2},支付 x 日元,并执行操作 x。如果您执行操作 x 当天 i,你获得 A_{i,x} 经验值。您每天不能执行一项以上的操作。

你被给予 Q 查询。在每个查询中,都会给出一对整数 (d, b) 这样 1 \leq d \leq N 和 0 \leq b \leq 2d。解决以下问题:

  • 假设您花费了 b 当天总计日元 1 到今天 d。在这些过程中您可以获得的最大可能总经验是多少 d 天?

你被给予 T 测试用例。解决它们中的每一个。

约束

  • 1 \leq T \leq 10^4
  • 1 \leq N \leq 2.5 \times 10^5
  • 1 \leq Q \leq 10^4
  • 0 \leq A_{i,x} \leq 10^9
  • 1 \leq d \leq N
  • 0 \leq b \leq 2d
  • 总和 N 所有测试用例最多 2.5 \times 10^5
  • 总和 Q 所有测试用例最多 10^4
  • 所有输入值均为整数

部分分数

此题得分不全。

  • 如果所有查询都满足 d = N,你会得到 5 点。

输入

输入由标准输入给出,格式如下:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

每个测试用例均按以下格式给出:

N Q
A_{1,0} A_{1,1} A_{1,2}
A_{2,0} A_{2,1} A_{2,2}
\vdots
A_{N,0} A_{N,1} A_{N,2}
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

每个查询均按以下格式给出:

d b

输出

按顺序输出所有测试用例的答案。
对于每个测试用例,打印 Q 行。上 i第行,输出答案 i-第一个查询。


示例输入 1

2
3 3
1 3 2
4 8 1
1 6 9
1 1
2 3
3 3
5 5
45 58 82
47 39 94
36 54 74
80 61 95
61 57 69
2 4
5 7
4 1
5 5
3 0

示例输出 1

3
10
18
176
387
226
371
128

例如,考虑 3-第一个测试用例的rd查询: d=3, b=3.
您可以获得的总体验 18 的最佳方式如下:

  • 天 1:选择 x=0。支付 0 日元和收益 A_{1,0}=1 经验。
  • 天 2:选择 x=1。支付 1 日元和收益 A_{2,1}=8 经验。
  • 天 3:选择 x=2。支付 2 日元和收益 A_{3,2}=9 经验。

示例输入 2

1
10 10
76 30 16
30 94 48
60 67 90
43 63 47
49 33 66
14 49 79
39 62 37
34 79 96
29 86 85
59 42 69
10 16
10 13
10 8
10 20
10 2
10 5
10 4
10 0
10 15
10 19

示例输出 2

764
770
724
633
554
664
634
433
780
679