NTUCPC Speed Run! #1 比賽已結束，感謝大家的參與！題目連結
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
4 . 飢腸鹿鹿
TopCoder
Tags
Description
馬車芽芽芽與鹿乃子乃子正享用著美味的柴鹿飯
將鹿角刨成薄片撒在飯上再淋上醬油，便是小鹿社中流行的一道美味料理——柴鹿飯。
今天鹿乃子乃子帶了 $N$ 支鹿角準備與社員分享，每一支鹿角有其各自的風味值 $f_i$ 以及滿足度 $s_i$。講究食物的馬車芽芽芽認為，最好吃的柴鹿飯應該要撒上 $K$ 支不同鹿角的薄片，並且撒上了多支鹿角的飯其整體風味值為各支鹿角的風味值的 XOR 和。
為了滿足不同人的喜好，馬車芽芽芽想要計算在不同整體風味值時，撒上的鹿角的滿足度總和最高可以是多少。為了不打擾馬車芽芽芽吃飯，請你寫一支程式幫助她。
Input Format
輸入的第一行包含三個整數 $N, K, C$，其中 $C$ 表示馬車芽芽芽想計算整體風味值為 $0$ 到 $C$ 的每個狀況。接下來 $N$ 行，每行包含兩個整數 $f_i, s_i$，表示第 $i$ 支鹿角的風味值及滿足度。
- $1 \le N \le 10^ 6$
- $1 \le K \le N$
- $0 \le C < 512$
- $0 \le f_i \le C$
- $1 \le s_i \le 10^ 9$
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
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
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
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 |