某街道上有 $n$ 支天線,每一支天線有其位置 $x$ 以及輻射範圍 $s$,將覆蓋範圍 $[x-s, x+s]$
這些天線可能沒有將整個街道都覆蓋住,所以需要花錢升級天線的覆蓋範圍
價格為範圍增加 $1$ 就要付出成本 $1$,也就是說成本 $p$ 能讓天線覆蓋範圍升級為 $[x-s-p, x+s+p]$
請算出覆蓋街道範圍 $[1, m]$ 的最小成本為何,如果天線範圍涵蓋到 $[1, m]$ 以外也沒關係
第 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$)
注意:在每個位置上最多只會有一支天線
輸出覆蓋整個街道 $[1, m]$ 的最小成本
第一筆測資有 $3$ 支天線,街道範圍 $[1, 595]$
其中一個覆蓋整個街道的方法為:
總成本 $38+213+35=286$
Codeforces 1253E Antenna Coverage
No. | Testdata Range | Score |
---|---|---|
1 | 0~54 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 262144 | 65536 | |
1 | 1000 | 262144 | 65536 | |
2 | 1000 | 262144 | 65536 | |
3 | 1000 | 262144 | 65536 | |
4 | 1000 | 262144 | 65536 | |
5 | 1000 | 262144 | 65536 | |
6 | 1000 | 262144 | 65536 | |
7 | 1000 | 262144 | 65536 | |
8 | 1000 | 262144 | 65536 | |
9 | 1000 | 262144 | 65536 | |
10 | 1000 | 262144 | 65536 | |
11 | 1000 | 262144 | 65536 | |
12 | 1000 | 262144 | 65536 | |
13 | 5000 | 262144 | 65536 | |
14 | 5000 | 262144 | 65536 | |
15 | 5000 | 262144 | 65536 | |
16 | 5000 | 262144 | 65536 | |
17 | 1000 | 262144 | 65536 | |
18 | 1000 | 262144 | 65536 | |
19 | 1000 | 262144 | 65536 | |
20 | 1000 | 262144 | 65536 | |
21 | 1000 | 262144 | 65536 | |
22 | 1000 | 262144 | 65536 | |
23 | 1000 | 262144 | 65536 | |
24 | 1000 | 262144 | 65536 | |
25 | 1000 | 262144 | 65536 | |
26 | 1000 | 262144 | 65536 | |
27 | 1000 | 262144 | 65536 | |
28 | 1000 | 262144 | 65536 | |
29 | 1000 | 262144 | 65536 | |
30 | 5000 | 262144 | 65536 | |
31 | 5000 | 262144 | 65536 | |
32 | 5000 | 262144 | 65536 | |
33 | 5000 | 262144 | 65536 | |
34 | 5000 | 262144 | 65536 | |
35 | 5000 | 262144 | 65536 | |
36 | 5000 | 262144 | 65536 | |
37 | 5000 | 262144 | 65536 | |
38 | 5000 | 262144 | 65536 | |
39 | 5000 | 262144 | 65536 | |
40 | 5000 | 262144 | 65536 | |
41 | 5000 | 262144 | 65536 | |
42 | 5000 | 262144 | 65536 | |
43 | 5000 | 262144 | 65536 | |
44 | 5000 | 262144 | 65536 | |
45 | 5000 | 262144 | 65536 | |
46 | 5000 | 262144 | 65536 | |
47 | 5000 | 262144 | 65536 | |
48 | 5000 | 262144 | 65536 | |
49 | 5000 | 262144 | 65536 | |
50 | 5000 | 262144 | 65536 | |
51 | 5000 | 262144 | 65536 | |
52 | 5000 | 262144 | 65536 | |
53 | 5000 | 262144 | 65536 | |
54 | 5000 | 262144 | 65536 |