TopCoder

Thumb maxresdefault
YenSean
Hello World!

User's AC Ratio

81.8% (9/11)

Submission's AC Ratio

18.4% (86/467)

Tags

Description

題目敘述請見此

注意本題輸入格式與上題有所不同。

Input Format

第一行包含兩個正整數$N, K$,代表小鎮裡有$N$戶居民(包含鎮長),並且你最多只能設立$K$個郵局。
接下來有一行包含$N$個非負整數$a_i$,代表所有居民的家離原點的距離。(所有居民都住在原點的同一側。)

對於所有測資,$K\leq N\leq 3\times 10^ 5, a_i\leq 10^ 9$。

子任務(測資) 額外限制 分數
1 (0~2) $N\leq 26$ 7
2 (0~5) $N\leq 700$ 19
3 (0~9) $N \leq 3000$ 27
4 (0~19) 無限制 47

Output Format

請輸出一個整數,代表每一戶人家到最近郵局的距離和最短為多少。

Sample Input

7 5
0 1 3 6 8 11 14

Sample Output

3

Hints

範例測資中,把郵局設在1、6、8、11、14即可。

Problem Source

TIOJ 1449進階版
Problem Set by Yihda Yol

Subtasks

For Testdata: 0 ~ 2, Score: 7
For Testdata: 0 ~ 5, Score: 19
For Testdata: 0 ~ 9, Score: 27
For Testdata: 0 ~ 19, Score: 47
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 900 131072 262144
1 900 131072 262144
2 900 131072 262144
3 900 131072 262144
4 900 131072 262144
5 900 131072 262144
6 900 131072 262144
7 900 131072 262144
8 900 131072 262144
9 900 131072 262144
10 1900 65536 262144
11 1900 65536 262144
12 1900 65536 262144
13 1900 65536 262144
14 1900 65536 262144
15 1900 65536 262144
16 1900 65536 262144
17 1900 65536 262144
18 1900 65536 262144
19 1900 65536 262144