1986 . 郵局設置問題 $\infty$EXTREME

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

72.0% (36/50)

Submission's AC Ratio

16.4% (217/1320)

Tags

DP-optimization DP

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 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