← 返回题目列表

AtCoder · nikkei2019_final_h

H. 家庭作业安排

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

配点 : 1500 点

問題文

从今天开始算 i 日 我们称之为 i 。 例如,今天是 Day 1明天是白天 2 。

真子桑, 编号至1 减去 N 包含 N 家庭作业。 她是日 从 1 开始 1 每天 选择并完成 1 家庭作业。 作业 i 天 A_i 或更早,她会 获得 X_i 分。 还有,日 如果您在 (A_i+1) 或之后完成, 获得Y_i 分。 在这里,X_i > Y_i 。

真子桑有每个 k (1 \leq k \leq N) 关于日 我想知道 k 可以获得的最高总分。 代表她提出这个要求。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq N
  • 1 \leq Y_i < X_i \leq 10^9
  • 所有输入值都是整数。 如果您想走

入力

输入是按以下格式从标准输入给出的。

N
A_1 X_1 Y_1
A_2 X_2 Y_2
\vdots
A_N X_N Y_N

出力

N 行。 k 这一天 打印到 k 为止获得的总分的最大值。


入力例 1

3
1 10 9
1 7 4
2 3 2

出力例 1

10
16
19

各 k 作业的最佳方式如下。 如果

k=1 ,日 关于 1 的家庭作业 如果你完成了 1 , 获得10 分。

k=2 ,日 关于 1 的家庭作业 如果你完成了 2 ,日 2 的家庭作业 如果你完成了 1 , 获得7+9=16 分。

k=3 ,日 关于 1 的家庭作业 如果你完成了 2 ,日 2 的家庭作业 如果你完成了 3 ,日 3 的家庭作业 如果你完成了 1 , 获得7+3+9=19 分。


入力例 2

6
2 58 37
2 67 12
3 82 79
4 23 6
4 82 64
1 40 17

出力例 2

82
164
231
289
309
328

入力例 3

15
9 605824191 280849371
4 596581791 33288517
9 721865638 162970480
3 973186445 472655273
6 305716162 49621035
8 630727512 144854327
5 314582040 241964889
2 837187623 326231876
1 619623058 10421080
9 938725073 25997036
2 256037683 12811156
8 930775386 430074396
9 724058993 159628544
9 519111960 59073187
3 157350380 35127939

出力例 3

973186445
1911911518
2842686904
3679874527
4403933520
5125799158
5756526670
6376149728
6981973919
7253580890
7495545779
7554618966
7604240001
7639367940
7652179096