804 . 置物櫃出租

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

80.0% (4/5)

Tags

apcsc apcsc-dp

Description

王老先生有一個置物櫃，共有 $M$ 個相同大小的格子，置物櫃目前已經租給 $n$ 個客戶，第 $i$ 位客戶所租的大小為 $f(i)$ 個格子（$1 \le i \le n$）。目前的承租量總和不超過 $M$，但是現在王老先生自己需要使用 $S$ 個格子的置物櫃，如果剩下的容量不夠，就必須退掉某些客戶的租約。假設每個客戶所租容量只能全退或全不退，而退租第 $i$ 個客戶失的利益與其所租容量 $f(i)$ 相同，請寫一支程式計算王老先生最小的損失利益，如果不須退租，則損失為 $0$。

Input Format

測試資料有兩行，第一行有三個正整數，依序是 $n$、$M$ 與 $S$，其中 $S \le M$，第二行是 $n$ 個正整數 $f(1), f(2), f(3), \ldots, f(n)$，同一行的數字間以空白隔開。

  • $1 \leq n \leq 100$
  • $1\le S\le M \leq 2\times 10^ 5$
  • $1\le f(i)\le M$，且 $f(i)$ 總和不超過 $M$。

Output Format

輸出王老先生最小的損失利益。

Sample Input 1

3 10 6
4 4 1

Sample Output 1

5

Sample Input 2

5 20 14
8 2 7 2 1

Sample Output 2

15

Hints

Problem Source

APCS 歷屆

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~23 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
23 1000 524288 65536 2
Submit
Back to Top