【題解】AtCoder ABC 167C – Skill Up

#include <iostream>
using namespace std;

int n, m, x, c[12], a[12][12];

int dp(int now, int choose[12], int tot[12]){
    if (now == n){
        for (int i = 0; i < m; i++){
            if (tot[i] < x) return -1;
        }
        int ret = 0;
        for (int i = 0; i < n; i++){
            if (choose[i]) ret += c[i];
        }
        return ret;
    }
    int mn = dp(now+1, choose, tot);
    for (int i = 0; i < m; i++){
        tot[i] += a[now][i];
    }
    choose[now] = 1;
    int ret = dp(now+1, choose, tot);
    for (int i = 0; i < m; i++){
        tot[i] -= a[now][i];
    }
    choose[now] = 0;
    if (mn == -1) mn = ret;
    else if (ret != -1 && ret < mn) mn = ret;
    return mn;
}

int main() {
    cin >> n >> m >> x;
    for (int i = 0; i < n; i++){
        cin >> c[i];
        for (int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }
    int _choose[12] = {}, _tot[12] = {};
    cout << dp(0, _choose, _tot) << "\n";
}