49 . 天線覆蓋問題

Submit
Status
Ranklist
Back to Problems List

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

50.0% (11/22)

Tags

2020 高階競技程式設計 - Contest #4

Description

某街道上有 $n$ 支天線，每一支天線有其位置 $x$ 以及輻射範圍 $s$，將覆蓋範圍 $[x-s, x+s]$

這些天線可能沒有將整個街道都覆蓋住，所以需要花錢升級天線的覆蓋範圍
價格為範圍增加 $1$ 就要付出成本 $1$，也就是說成本 $p$ 能讓天線覆蓋範圍升級為 $[x-s-p, x+s+p]$

請算出覆蓋街道範圍 $[1, m]$ 的最小成本為何，如果天線範圍涵蓋到 $[1, m]$ 以外也沒關係

Input Format

第 1 列有數字 $n, m$ 代表天線數量，以及街道範圍 ($1 \le n \le 80, n \le m \le 10^ 5$)
接著有 $n$ 列數字 $x_i, s_i$ 表示天線 $i$ 的位置以及輻射範圍 ($1 \le x_i \le m, 0 \le s_i \le m$)

注意：在每個位置上最多只會有一支天線

Output Format

輸出覆蓋整個街道 $[1, m]$ 的最小成本

Sample Input 1

3 595
42 3
300 3
555 5

Sample Output 1

286

Sample Input 2

1 1
1 1

Sample Output 2

0

Sample Input 3

2 55
20 0
3 9

Sample Output 3

35

Sample Input 4

4 100
87 2
2 9
38 7
21 5

Sample Output 4

39

Hints

第一筆測資有 $3$ 支天線，街道範圍 $[1, 595]$
其中一個覆蓋整個街道的方法為：

  • 花 $38$ 成本將位置 $42$ 的天線升級為 $[42-3-38, 42+3+38] = [1, 83]$
  • 花 $213$ 成本將位置 $300$ 的天線升級為 $[300-3-213, 300+3+213] = [84, 516]$
  • 花 $35$ 成本將位置 $555$ 的天線升級為 $[555-5-35, 555+5+35] = [515, 595]$

總成本 $38+213+35=286$

Problem Source

Codeforces 1253E Antenna Coverage

Subtasks

No. Testdata Range Score
1 0~54 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1
1 1000 262144 65536 1
2 1000 262144 65536 1
3 1000 262144 65536 1
4 1000 262144 65536 1
5 1000 262144 65536 1
6 1000 262144 65536 1
7 1000 262144 65536 1
8 1000 262144 65536 1
9 1000 262144 65536 1
10 1000 262144 65536 1
11 1000 262144 65536 1
12 1000 262144 65536 1
13 5000 262144 65536 1
14 5000 262144 65536 1
15 5000 262144 65536 1
16 5000 262144 65536 1
17 1000 262144 65536 1
18 1000 262144 65536 1
19 1000 262144 65536 1
20 1000 262144 65536 1
21 1000 262144 65536 1
22 1000 262144 65536 1
23 1000 262144 65536 1
24 1000 262144 65536 1
25 1000 262144 65536 1
26 1000 262144 65536 1
27 1000 262144 65536 1
28 1000 262144 65536 1
29 1000 262144 65536 1
30 5000 262144 65536 1
31 5000 262144 65536 1
32 5000 262144 65536 1
33 5000 262144 65536 1
34 5000 262144 65536 1
35 5000 262144 65536 1
36 5000 262144 65536 1
37 5000 262144 65536 1
38 5000 262144 65536 1
39 5000 262144 65536 1
40 5000 262144 65536 1
41 5000 262144 65536 1
42 5000 262144 65536 1
43 5000 262144 65536 1
44 5000 262144 65536 1
45 5000 262144 65536 1
46 5000 262144 65536 1
47 5000 262144 65536 1
48 5000 262144 65536 1
49 5000 262144 65536 1
50 5000 262144 65536 1
51 5000 262144 65536 1
52 5000 262144 65536 1
53 5000 262144 65536 1
54 5000 262144 65536 1
Submit
Status
Ranklist
Back to Top