1986 . 郵局設置問題 ∞EXTREME

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Adrien Wu
AC×29New TIOJ ?

User's AC Ratio

70.6% (36/51)

Submission's AC Ratio

16.4% (217/1327)

Tags

DP-optimization DP

Description

題目敘述請見此。

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

Input Format

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

對於所有測資，K≤N≤3×105,ai≤109。

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

Output Format

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

Sample Input 1

7 5
0 1 3 6 8 11 14

Sample Output 1

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 (VSS, 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
Submit
Back to Top