112 . Watching Fireworks is Fun

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

100.0% (7/7)

Tags

ioicamp ioicamp-2023

Description

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

Input Format

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

接下來的 $M$ 行每行恰有三個正整數 $a_i, b_i, t_i$ 以一個空白隔開。

  • $1 \le N \le 150000$
  • $1 \le M \le 300$
  • $1 \le D \le N$
  • $1 \le a_i \le N$
  • $1 \le b_i \le 10^ 9$
  • $1 \le t_i \le 10^ 9$
  • $t_i \le t_{i+1}$ 對於所有 $1 \le 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