USACO-T024: Healthy Holsteins

/*
ID: mickyta1
TASK: holstein
LANG: C++
*/

#include <bits/stdc++.h>
using namespace std;

const int N = 15 + 5;
const int V = 25 + 5;

vector<int> tmp;
int rq[V], sum[V], vit[N][V];

int main(){
    freopen("holstein.in", "r", stdin);
    freopen("holstein.out", "w", stdout);

    int nVit;
    scanf("%d", &nVit);
    for(int i = 1; i <= nVit; ++i){
        scanf("%d", &rq[i]);
    }
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= nVit; ++j){
            scanf("%d", &vit[i][j]);
        }
    }
    int ansBit = n;
    int ans = (1 << n) - 1;
    for(int b = 1; b < (1 << n); ++b){
        int bitCnt = 0;
        for(int i = 1; i <= nVit; ++i){
            sum[i] = 0;
        }
        for(int e = 1; e <= n; ++e){
            if((b & (1 << (e - 1))) != 0){
                for(int i = 1; i <= nVit; ++i){
                    sum[i] += vit[e][i];
                }
                ++bitCnt;
            }
        }
        int ok = true;
        for(int i = 1; i <= nVit; ++i){
            if(sum[i] < rq[i]){
                ok = false;
                break;
            }
        }
        if(!ok){
            continue;
        }
        if(bitCnt < ansBit){
            ansBit = bitCnt;
            ans = b;
        } else if(bitCnt == ansBit){
            if((b & -b) < (ans & -ans)){
                ans = b;
            }
        }
    }
    cout << ansBit << ' ';
    for(int e = 1; e <= n; ++e){
        if((ans & (1 << (e - 1))) != 0){
            tmp.push_back(e);
        }
    }
    for(int i = 0; i < (int)tmp.size() - 1; ++i){
        cout << tmp[i] << ' ';
    }
    cout << tmp.back() << '\n';

    fclose(stdin);
    fclose(stdout);
    return 0;
}