fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. ll n,k,osum;
  7. ll a[21],sol[21];
  8.  
  9. int safe(int x,ll sum)
  10. {
  11.     if((a[x] + sum <= osum) && (sol[x] != 1))
  12.         return 1;
  13.     else
  14.         return 0;
  15. }
  16.  
  17. int solve(ll sum,int j)
  18. {
  19.  
  20.     if(sum == osum/k)
  21.     {
  22.         return 1;
  23.     }
  24.  
  25.     for(int i=j;i<n;i++)
  26.     {
  27.         if(safe(i,sum))
  28.         {
  29.             sol[i]=1;
  30.             sum += a[i];
  31.             if(solve(sum,i+1))
  32.             {
  33.                 return 1;
  34.             }
  35.             else
  36.             {
  37.                 sol[i]=-1;
  38.                 sum -= a[i];
  39.             }
  40.         }
  41.         if(solve(sum,i+1))
  42.         {
  43.             return 1;
  44.         }
  45.     }
  46.     return 0;
  47. }
  48.  
  49.  
  50.  
  51. int calc()
  52. {
  53.          scanf("%lld%lld",&n,&k);
  54.  
  55.         for(int i=0;i<n;i++)
  56.         {
  57.             scanf("%lld",&a[i]);
  58.             osum += a[i];
  59.             sol[i]=-1;
  60.         }
  61.  
  62.         if(osum%k != 0)
  63.         {
  64.            printf("no\n");
  65.             return 0;
  66.         }
  67.         for(int i=0;i<k;i++)
  68.         {
  69.             if(!solve(0,0))
  70.             {
  71.                 printf("no\n");
  72.                return 0;
  73.             }
  74.  
  75.         }
  76.          printf("yes\n");
  77.         return 1;
  78. }
  79.  
  80. int main()
  81. {
  82.     #ifndef ONLINE_JUDGE
  83.     freopen("in.txt","r",stdin);
  84.     #endif
  85.  
  86.     int t;
  87.     scanf("%d",&t);
  88.  
  89.  
  90.     while(t--)
  91.     {
  92.         osum=0;
  93.         calc();
  94.     }
  95.  
  96.  
  97.     return 0;
  98. }
  99.  
Success #stdin #stdout 0s 3144KB
comments (?)
stdin
copy 
2
5 3
1 2 4 5 6
5 3
1 2 4 5 7
stdout
copy 
yes
no
https://ideone.com/DcFPqL
language:
C++ (gcc 8.3)
created:
8 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!