fork(2) download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <sstream> 
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <queue>
  9. #include <stack>
  10. #include <cmath>
  11. #include <algorithm>
  12. #include <cstring>
  13. #include <ctime>
  14. using namespace std;
  15. #define pb push_back
  16. #define mp make_pair
  17. #define pii pair<int,int>
  18. #define vi vector<int>
  19. #define SZ(x) ((int)(x.size()))
  20. #define fi first
  21. #define se second
  22. #define FOR(i,n) for(int (i)=0;(i)<(n);++(i))
  23. #define FORI(i,n) for(int (i)=1;(i)<=(n);++(i))
  24. #define IN(x,y) ((y).find((x))!=(y).end())
  25. #define ALL(t) t.begin(),t.end()
  26. #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
  27. #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
  28. #define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
  29. #define REMAX(a,b) (a)=max((a),(b));
  30. #define REMIN(a,b) (a)=min((a),(b));
  31. #define DBG cerr << "debug here" << endl;
  32. #define DBGV(vari) cerr << #vari<< " = "<< (vari) <<endl;
  33.  
  34. typedef long long ll;
  35.  
  36. const int MAXK = 8;
  37. const int MAXN = 21;
  38.  
  39. ll a[MAXN];
  40. bool dp[MAXK + 1][1LL << MAXN];
  41. int n, k;
  42.  
  43. bool solve()
  44. {
  45.     ll sum = 0;
  46.     FOR(i, n) sum += a[i];
  47.     if((sum % k != 0) || (n < k)) return 0;
  48.     if(sum == 0) return 1;
  49.     ll x = sum / k;
  50.     ll maxBit = (1LL << n);
  51.     REP(i, 0, k) FOR(j, maxBit) dp[i][j] = 0;
  52.     dp[0][0] = 1;
  53.     FOR(i, k)
  54.     {
  55.         for(ll mask = 0; mask < maxBit; ++mask)
  56.         {
  57.             if(!dp[i][mask]) continue;
  58.             sum = 0;
  59.             FOR(j, n) sum += ((mask & (1LL << j)) > 0) * a[j];
  60.             sum -= i * x;
  61.             FOR(j, n)
  62.             {
  63.                 if(mask & (1LL << j)) continue;
  64.                 ll new_mask = mask | (1LL << j);
  65.                 if(sum + a[j] == x)
  66.                 {
  67.                     dp[i + 1][new_mask] = 1;
  68.                 }
  69.                 else if(sum + a[j] < x)
  70.                 {
  71.                     dp[i][new_mask] = 1;
  72.                 }
  73.             }
  74.         } 
  75.     }
  76.     return dp[k][maxBit - 1];
  77. }
  78. int main()
  79. {
  80.     int t;
  81.     cin >> t;
  82.     while(t--)
  83.     {
  84.         cin >> n >> k;
  85.         FOR(i, n) cin >> a[i]; 
  86.         bool res = solve();   
  87.         cout << (res ? "yes" : "no") << endl;
  88.     }
  89.     return 0;
  90. }
Time limit exceeded #stdin #stdout 5s 21736KB
comments (?)
stdin
copy 
10
21 7
10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000
21 7
10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000
21 7
10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000
21 7
10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000
21 7
10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000
21 7
10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000
21 7
10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000
21 7
10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000
21 7
10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000
21 7
10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000 10000000000
stdout
copy 
yes
yes
yes
yes
yes
yes
https://ideone.com/EtDTSI
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!