112 . Watching Fireworks is Fun

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

92.3% (12/13)

Submission's AC Ratio

58.3% (14/24)

Tags

ioicamp ioicamp-2023

Description

有 M 個煙火將在一維數線上綻放。第 i 個煙火在時間 ti 、於位置 ai 綻放，其中 1≤ai≤N。如果你在位置 1≤x≤N 觀看煙火 i 的話，你會獲得 bi−|ai−x| 的開心度。此外，你每秒可以移動 d 單位的距離，且不能離開 1 到 N 的位置範圍。你可以任選初始位置，請問看完 M 個煙火所獲得的總開心度最大能多少。

Input Format

在第一行共有三個正整數 N,M,D 以一個空白隔開。

接下來的 M 行每行恰有三個正整數 ai,bi,ti 以一個空白隔開。

  • 1≤N≤150000
  • 1≤M≤300
  • 1≤D≤N
  • 1≤ai≤N
  • 1≤bi≤109
  • 1≤ti≤109
  • ti≤ti+1 對於所有 1≤i<M

Output Format

請輸出一個整數代表答案。

Sample Input 1

80 4 1
50 1 1
79 1 4
1 1 6
30 2 13

Sample Output 1

-79

Hints

Problem Source

IOICamp 2023 Day3 pD / Codeforces 372C

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~24 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
23 1000 524288 65536 2
24 1000 524288 65536 2
Submit
Back to Top