Advertisement
mickypinata

USACO-T024: Healthy Holsteins

Nov 29th, 2021
465
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: holstein
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. const int N = 15 + 5;
  11. const int V = 25 + 5;
  12.  
  13. vector<int> tmp;
  14. int rq[V], sum[V], vit[N][V];
  15.  
  16. int main(){
  17.     freopen("holstein.in", "r", stdin);
  18.     freopen("holstein.out", "w", stdout);
  19.  
  20.     int nVit;
  21.     scanf("%d", &nVit);
  22.     for(int i = 1; i <= nVit; ++i){
  23.         scanf("%d", &rq[i]);
  24.     }
  25.     int n;
  26.     scanf("%d", &n);
  27.     for(int i = 1; i <= n; ++i){
  28.         for(int j = 1; j <= nVit; ++j){
  29.             scanf("%d", &vit[i][j]);
  30.         }
  31.     }
  32.     int ansBit = n;
  33.     int ans = (1 << n) - 1;
  34.     for(int b = 1; b < (1 << n); ++b){
  35.         int bitCnt = 0;
  36.         for(int i = 1; i <= nVit; ++i){
  37.             sum[i] = 0;
  38.         }
  39.         for(int e = 1; e <= n; ++e){
  40.             if((b & (1 << (e - 1))) != 0){
  41.                 for(int i = 1; i <= nVit; ++i){
  42.                     sum[i] += vit[e][i];
  43.                 }
  44.                 ++bitCnt;
  45.             }
  46.         }
  47.         int ok = true;
  48.         for(int i = 1; i <= nVit; ++i){
  49.             if(sum[i] < rq[i]){
  50.                 ok = false;
  51.                 break;
  52.             }
  53.         }
  54.         if(!ok){
  55.             continue;
  56.         }
  57.         if(bitCnt < ansBit){
  58.             ansBit = bitCnt;
  59.             ans = b;
  60.         } else if(bitCnt == ansBit){
  61.             if((b & -b) < (ans & -ans)){
  62.                 ans = b;
  63.             }
  64.         }
  65.     }
  66.     cout << ansBit << ' ';
  67.     for(int e = 1; e <= n; ++e){
  68.         if((ans & (1 << (e - 1))) != 0){
  69.             tmp.push_back(e);
  70.         }
  71.     }
  72.     for(int i = 0; i < (int)tmp.size() - 1; ++i){
  73.         cout << tmp[i] << ' ';
  74.     }
  75.     cout << tmp.back() << '\n';
  76.  
  77.     fclose(stdin);
  78.     fclose(stdout);
  79.     return 0;
  80. }
  81.  
Advertisement
RAW Paste Data Copied
Advertisement