ccbeginner

UVa Q10364

Jan 21st, 2020
111
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q10364
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int n,m, cnt, vis;
  6. int arr[20];
  7. bool rec[1<<20];
  8. int clen, tlen;//current, target
  9. bool yes;
  10.  
  11. bool cmp(int a, int b){return a > b;}
  12.  
  13. void dfs(){
  14.     //cout << clen << ' ' << tlen << ' ' << cnt << endl;
  15.     if(cnt == 3){
  16.         yes = 1;
  17.         return;
  18.     }
  19.     int one = -1;
  20.     for(int i = 0; i < m; ++i){
  21.         if(!(vis & (1<<i)) && arr[i] <= tlen - clen){
  22.             one = i;
  23.             break;
  24.         }
  25.     }
  26.     if(one == -1)return;
  27.     if(arr[one] == tlen - clen){//match
  28.         clen = 0;
  29.         vis += (1<<one);
  30.         ++cnt;
  31.         if(!rec[vis]){
  32.             dfs();
  33.             rec[vis] = 1;
  34.         }
  35.         --cnt;
  36.         vis -= (1<<one);
  37.         clen = tlen-arr[one];
  38.     }else{
  39.         for(one; one < m && !yes; ++one){
  40.             if(!(vis & (1<<one))){
  41.                 clen += arr[one];
  42.                 vis += (1<<one);
  43.                 if(!rec[vis]){
  44.                     dfs();
  45.                     rec[vis] = 1;
  46.                 }
  47.                 vis -= (1<<one);
  48.                 clen -=arr[one];
  49.             }
  50.         }
  51.     }
  52. }
  53.  
  54. int32_t main(){
  55.     cin >> n;
  56.     while(n--){
  57.         vis = cnt = clen = tlen = 0;
  58.         yes = 0;
  59.         memset(rec, 0, sizeof(rec));
  60.         cin >> m;
  61.         for(int i = 0; i < m; ++i){
  62.             cin >> arr[i];
  63.             tlen += arr[i];
  64.         }
  65.         if(tlen % 4 != 0){
  66.             cout << "no\n";
  67.         }else{
  68.             sort(arr, arr+m, cmp);
  69.             tlen /= 4;
  70.             dfs();
  71.             if(yes)cout << "yes\n";
  72.             else cout << "no\n";
  73.         }
  74.     }
  75.     return 0;
  76. }
RAW Paste Data