← 返回题目列表

AtCoder · cpsco2019_s1_f

F. 当季水果

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

配点 : 600 点

問題文

天妇罗君是一种水果 我有 N 件。从今天开始 N 我决定一天内吃掉所有的水果。

每天他都买当时剩下的水果。 1 选一个然后吃。1 吃完水果后,当天就会吃完。

果物 i 是季节性的 t_i 已确定,味道会根据季节和吃水果的日期而变化。

果物 i 在 t_i 第一天吃多好吃? A_i 和t_i 从第一天开始 1 天天吃的美味 B_i 。更准确地说,水果 i (1\le i\le N) 在 j 日目 (1\le j\le N) 吃起来有多好吃? 可以表示为 A_i -|j-t_i|\times B_i 。

他获得的满意度是 N 这是一天吃到的水果的美味度最小值。

求当天妇罗君吃的顺序适当时他能获得的最大满足程度。

制約

  • 1\le N\le 2\times 10^4
  • 1\le t_i\le N
  • 0\le A_i\le 10^9
  • 1\le B_i\le 5\times 10^4
  • 输入全部为整数

入力

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

N
t_1\ A_1\ B_1
t_2\ A_2\ B_2
\vdots
t_N\ A_N\ B_N

出力

天妇罗君的最大满意度是 请在 1 行输出。


入力例 1

3
1 7 1
1 6 3
2 5 2

出力例 1

5

1 当天水果 2 吃起来很好吃。 6-|1-1|\times 3 = 6 。

2 当天水果 3 吃起来很好吃。 5-|2-2|\times 2 = 5 。

3 当天水果 1 吃起来很好吃。 7-|3-1|\times 1 = 5 。

此时的满意度为 5 ,这是最大值。


入力例 2

2
2 0 1
2 0 1

出力例 2

-1

满意度也可能是负面的。


入力例 3

10
3 78 4
1 97 8
4 93 7
1 72 5
5 81 6
9 70 9
2 72 3
6 84 5
5 83 9
3 79 2

出力例 3

65