1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#define MAX(x,y) ((x)>(y)?(x):(y))
int main() {
    int bitsum[512], best[1001][1024] = {}, w[1000];
    int n, m, q, ans = 0;
    int i, j, k;
    bitsum[0] = 0;
    for(i = 1; i < 512; i *= 2)
        for(j = i; j < 2 * i; j++)
            bitsum[j] = bitsum[j - i] + 1;
    scanf("%d%d%d", &n, &m, &q);
    for(i = 0; i < n; i++)
        scanf("%d", &w[i]);
    for(i = 0; i < m; i++)
        for(j = 0, k = (1 << i); j < k; j++) {
            best[i+1][j] = MAX(best[i+1][j], best[i][j]);
            if(bitsum[j] < q)
                best[i+1][j+k] = MAX(best[i+1][j+k], best[i][j] + w[i]);
        }
    for(i = m, k = (1 << m); i < n; i++)
            for(j = 0; j < k; j++) {
                best[i+1][j/2] = MAX(best[i+1][j/2], best[i][j]);
                if(bitsum[j/2] < q)
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX