4 . 飢腸鹿鹿

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

66.7% (8/12)

Submission's AC Ratio

50.0% (16/32)

Tags

ntucpc-challenge1

Description


馬車芽芽芽與鹿乃子乃子正享用著美味的柴鹿飯

將鹿角刨成薄片撒在飯上再淋上醬油，便是小鹿社中流行的一道美味料理——柴鹿飯。

今天鹿乃子乃子帶了 N 支鹿角準備與社員分享，每一支鹿角有其各自的風味值 fi 以及滿足度 si。講究食物的馬車芽芽芽認為，最好吃的柴鹿飯應該要撒上 K 支不同鹿角的薄片，並且撒上了多支鹿角的飯其整體風味值為各支鹿角的風味值的 XOR 和。

為了滿足不同人的喜好，馬車芽芽芽想要計算在不同整體風味值時，撒上的鹿角的滿足度總和最高可以是多少。為了不打擾馬車芽芽芽吃飯，請你寫一支程式幫助她。

Input Format

輸入的第一行包含三個整數 N,K,C，其中 C 表示馬車芽芽芽想計算整體風味值為 0 到 C 的每個狀況。接下來 N 行，每行包含兩個整數 fi,si，表示第 i 支鹿角的風味值及滿足度。

  • 1≤N≤106
  • 1≤K≤N
  • 0≤C<512
  • 0≤fi≤C
  • 1≤si≤109

Output Format

輸出一行包含 C+1 個整數，其中第 i 個整數表示整體風味值為 i−1 的狀況，若無法得到 i−1 的整體風味值，請輸出 -1；否則，請輸出整體風味值為 i−1 時最高的滿足度總和。

Sample Input 1

4 2 7
4 2
3 3
2 5
6 6

Sample Output 1

-1 8 8 -1 11 9 7 5

Sample Input 2

10 7 10
3 23
4 46
0 27
6 32
3 36
5 31
10 43
0 24
10 5
6 41

Sample Output 2

207 236 237 208 229 214 215 230 256 225 226

Sample Input 3

4 4 0
0 123456789
0 864197532
0 987654321
0 1000000000

Sample Output 3

2975308642

Hints

第一筆範例測資中，有 6 種挑選 2 支鹿角的方法，其整體風味值及滿足度總和分別如下：

  • 挑選第 1 支及第 2 支鹿角：整體風味值為 7，滿足度為 5。
  • 挑選第 1 支及第 3 支鹿角：整體風味值為 6，滿足度為 7。
  • 挑選第 1 支及第 4 支鹿角：整體風味值為 2，滿足度為 8。
  • 挑選第 2 支及第 3 支鹿角：整體風味值為 1，滿足度為 8。
  • 挑選第 2 支及第 4 支鹿角：整體風味值為 5，滿足度為 9。
  • 挑選第 3 支及第 4 支鹿角：整體風味值為 4，滿足度為 11。

Problem Source

改編自 2024 台清交程式競賽 pF - Choosing Model Rockets

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~57, 100~101 C<64 20
3 0~103 無額外限制 80

Testdata and Limits

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