TopCoder

Thumb maxresdefault
YenSean
Hello World!

User's AC Ratio

76.9% (10/13)

Submission's AC Ratio

18.5% (87/470)

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

No. Testdata Range Score
1 0~2 7
2 0~5 19
3 0~9 27
4 0~19 47

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 900 131072 262144 1 2 3 4
1 900 131072 262144 1 2 3 4
2 900 131072 262144 1 2 3 4
3 900 131072 262144 2 3 4
4 900 131072 262144 2 3 4
5 900 131072 262144 2 3 4
6 900 131072 262144 3 4
7 900 131072 262144 3 4
8 900 131072 262144 3 4
9 900 131072 262144 3 4
10 1900 65536 262144 4
11 1900 65536 262144 4
12 1900 65536 262144 4
13 1900 65536 262144 4
14 1900 65536 262144 4
15 1900 65536 262144 4
16 1900 65536 262144 4
17 1900 65536 262144 4
18 1900 65536 262144 4
19 1900 65536 262144 4