919 . 我獨自升級

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

蔡兆豐
大家好，我是蔡兆豐。我們今天要介紹的書是我兒佳比。這本書是在講述一個名叫科。克萊爾的傳奇故事。他本來居住在童話社區，每個人都被要求。要一樣。

User's AC Ratio

81.8% (18/22)

Submission's AC Ratio

64.2% (34/53)

Tags

ioicamp ioicamp-2025

Description

A 子是一位經驗老到的實況主，面對來自網路上的攻擊與誹謗，他早有所準備，將自己化為多個身份，形成一人包圍網搭配最強律師使用法律鐵拳合力對抗敵人們。

A 子一共有 $N$ 個不同的身份，其中第 $i$ 個身份有著強度 $s_i$。最近他感到分身乏術，雖然發起攻擊才能對敵人造成傷害，但防禦來自敵人的攻擊，降低炎上的機會也是相當重要的。A 子認為他的弱點便是目前強度最低的身份，他決定透過吸收 $M$ 隻貓咪的靈魂來增強自己的弱點。每吸收一隻貓咪的靈魂，他便能增強目前的弱點，將該身份的強度增加 $C$。如果有多個強度 $s_i$ 最低的身份，他會選擇最前面的身份加強，也就是 $i$ 最小的一個。

A 子做事從不馬虎，必先縝密規劃，在準備好之前絕不走漏風聲。他想先知道，在吸收 $M$ 隻貓咪的靈魂後，其弱點的強度會是多少？

Input Format

輸入的第一行包含三個正整數 $N,M,C$，表示身份的數量、貓咪的數量、每隻貓咪的靈魂能提供的強度。第二行包含 $N$ 個正整數 $s_i$，表示一開始每個身份的強度。

  • $1 \le N \le 3 \times 10^ 5$
  • $1 \le M \le 10^ 9$
  • $1 \le C \le 10^ 9$
  • $1 \le s_i \le 10^ 9$

Output Format

輸出一個整數，表示吸收 $M$ 隻貓咪的靈魂後，其弱點的強度會是多少。

Sample Input 1

5 4 3
3 1 4 1 5

Sample Output 1

4

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 1~7 $s_1 = s_2 = \ldots = s_N$ 4
3 8~16 $1 \le N \le 3000$ 且 $1 \le M \le 3000$ 7
4 8~29 $1 \le N \le 3000$ 24
5 8~16, 30~42 $1 \le M \le 3000$ 10
6 43~55 $C=1$ 23
7 0~85 無額外限制 32

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 1048576 65536 1 7
1 1000 1048576 65536 2 7
2 1000 1048576 65536 2 7
3 1000 1048576 65536 2 7
4 1000 1048576 65536 2 7
5 1000 1048576 65536 2 7
6 1000 1048576 65536 2 7
7 1000 1048576 65536 2 7
8 1000 1048576 65536 3 4 5 7
9 1000 1048576 65536 3 4 5 7
10 1000 1048576 65536 3 4 5 7
11 1000 1048576 65536 3 4 5 7
12 1000 1048576 65536 3 4 5 7
13 1000 1048576 65536 3 4 5 7
14 1000 1048576 65536 3 4 5 7
15 1000 1048576 65536 3 4 5 7
16 1000 1048576 65536 3 4 5 7
17 1000 1048576 65536 4 7
18 1000 1048576 65536 4 7
19 1000 1048576 65536 4 7
20 1000 1048576 65536 4 7
21 1000 1048576 65536 4 7
22 1000 1048576 65536 4 7
23 1000 1048576 65536 4 7
24 1000 1048576 65536 4 7
25 1000 1048576 65536 4 7
26 1000 1048576 65536 4 7
27 1000 1048576 65536 4 7
28 1000 1048576 65536 4 7
29 1000 1048576 65536 4 7
30 1000 1048576 65536 5 7
31 1000 1048576 65536 5 7
32 1000 1048576 65536 5 7
33 1000 1048576 65536 5 7
34 1000 1048576 65536 5 7
35 1000 1048576 65536 5 7
36 1000 1048576 65536 5 7
37 1000 1048576 65536 5 7
38 1000 1048576 65536 5 7
39 1000 1048576 65536 5 7
40 1000 1048576 65536 5 7
41 1000 1048576 65536 5 7
42 1000 1048576 65536 5 7
43 1000 1048576 65536 6 7
44 1000 1048576 65536 6 7
45 1000 1048576 65536 6 7
46 1000 1048576 65536 6 7
47 1000 1048576 65536 6 7
48 1000 1048576 65536 6 7
49 1000 1048576 65536 6 7
50 1000 1048576 65536 6 7
51 1000 1048576 65536 6 7
52 1000 1048576 65536 6 7
53 1000 1048576 65536 6 7
54 1000 1048576 65536 6 7
55 1000 1048576 65536 6 7
56 1000 1048576 65536 7
57 1000 1048576 65536 7
58 1000 1048576 65536 7
59 1000 1048576 65536 7
60 1000 1048576 65536 7
61 1000 1048576 65536 7
62 1000 1048576 65536 7
63 1000 1048576 65536 7
64 1000 1048576 65536 7
65 1000 1048576 65536 7
66 1000 1048576 65536 7
67 1000 1048576 65536 7
68 1000 1048576 65536 7
69 1000 1048576 65536 7
70 1000 1048576 65536 7
71 1000 1048576 65536 7
72 1000 1048576 65536 7
73 1000 1048576 65536 7
74 1000 1048576 65536 7
75 1000 1048576 65536 7
76 1000 1048576 65536 7
77 1000 1048576 65536 7
78 1000 1048576 65536 7
79 1000 1048576 65536 7
80 1000 1048576 65536 7
81 1000 1048576 65536 7
82 1000 1048576 65536 7
83 1000 1048576 65536 7
84 1000 1048576 65536 7
85 1000 1048576 65536 7
Submit
Back to Top