fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define for1(i,m,n) for(int i=m;i<=n;i++)
  5. #define for0(i,m,n) for(int i=m;i<n;i++)
  6. #define forr1(i,m,n) for(int i=m;i>=n;i--)
  7. #define forr2(i,m,n) for(int i=m;i>n;i--)
  8.  
  9. #define el '\n'
  10. #define fi first
  11. #define se second
  12. #define ii pair<int,int>
  13. #define vll(i) i.begin(),i.end()
  14. #define pb push_back
  15. #define fr front()
  16.  
  17. #define MASK(i) ((1ll) << (i))
  18. #define BIT(i,n) (((i)>>(n))&1)
  19.  
  20. const int N=16;
  21. const int MOD=1e9+2277;
  22.  
  23. int a[MASK(N)+3],s[MASK(N)+3];
  24. bool ok[MASK(N)+3];
  25.  
  26. int main() {
  27.     ios::sync_with_stdio(0);
  28.     cin.tie(0);
  29.     cout.tie(0);
  30. //    freopen("message.inp", "r", stdin);
  31. //    freopen("message.out", "w", stdout);
  32. int n,k,sumn=0;cin>>n>>k;
  33.  
  34. for0(i,0,n){
  35.  cin>>a[i];
  36.  sumn+=a[i];
  37. }
  38. if(sumn%k!=0) {
  39.     cout<<false;
  40.     return 0;
  41. }
  42. sumn/=k;
  43.  
  44. for0(i,0,n){
  45.  s[MASK(i)]=a[i];
  46. }
  47.  
  48. for0(i,0,MASK(n))
  49.     if(__builtin_popcount(i)>=2){
  50.      int tmp=i&-i;
  51.      s[i]=s[tmp]+s[i^tmp];
  52.  
  53. }
  54. ok[0]=1;
  55. for0(i,1,MASK(n)){
  56.   //ok[i]=0;
  57.   forr1(j,i,0){
  58.    j&=i;
  59.    if(s[j]==sumn&&ok[i^j]) {
  60.         //cout<<i<<el;
  61.         ok[i]=1;
  62.    break;
  63.    }
  64.   }
  65. }
  66. cout<<ok[MASK(n)-1];
  67.     return 0;
  68. }
  69.  
Success #stdin #stdout 0.01s 5264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/yo6w9t
dp bitmask: chia day thanh k phan bang nhau
language:
C++14 (gcc 8.3)
created:
13 days 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!