1480번: 보석 모으기

https://www.acmicpc.net/problem/1480

#include<cstdio>
int n, m, c, a[13], dp[1 << 13], r;
int main() {
    scanf("%d%d%d", &n, &m, &c);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    for (int i = 1; i < 1 << n; i++) {
        int s = 0, t = 0;
        for (int j = 0; j < n; j++) if (1 << j&i) s += a[j], t++;
        dp[i] = s > c ? 1e9 : 1;
        for (int j = 1; j < i; j++) if ((i | j) == i && dp[j] + dp[i^j] < dp[i]) dp[i] = dp[j] + dp[i^j];
        if (dp[i] <= m && t > r) r = t;
    }
    printf("%d", r);
    return 0;
}