fork download
copy 
  1. //----->|try=0; while(!success) try++;|<------
  2. //----->|Belief Yourself,Respect Yourself|<----
  3. //----->|Be Proud Of Yourself,You're Doing Your best|<-----
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. #define uniq(x)  x.erase(unique(x.begin(),x.end()), x.end()) //Unique value find from vector
  7. #define upper(arr,n,fixed) upper_bound(arr,arr+n,fixed)-arr  //Upper value search;
  8. #define lower(arr,n,fixed) upper_bound(arr,arr+n,fixed)-arr  //Lower value search;
  9. #define max3(a,b,c) max(max(a,b),c)//maximum value find three value;
  10. #define min3(a,b,c) min(min(a,b),c)//minimum value find three value;
  11. #define PI acos(-1.0)//PI Calculation
  12. #define LL long long
  13. #define AND(a,b) ((a) & (b))
  14. #define OR(a,b) ((a)|(b))
  15. #define XOR(a,b) ((a) ^ (b))
  16. #define mp make_pair
  17. #define sqr(x) ((x)*(x))
  18. #define sqrt(x) sqrt(1.0*(x))
  19. #define INF_MAX 2147483647
  20. #define INF_MIN -2147483647
  21. #define MX 1000005
  22. #define MOD 1000000007
  23. template<typename T> T POW(T b,T p)          //Pow calculation
  24.  {
  25.     T r=1;
  26.     while(p) {
  27.         if(p&1)r=(r*b);
  28.         b=(b*b);
  29.         p>>=1;
  30.     }
  31.     return r;
  32. }
  33.  
  34. template<typename T> T BigMod(T b,T p,T m) //BigMod Calculation
  35. {
  36.     T r=1;
  37.     while(p) {
  38.         if(p&1)r=(r*b)%m;
  39.         b=(b*b)%m;
  40.         p>>=1;
  41.     }
  42.     return r;
  43. }
  44.  
  45. //||--------------------------->||Main_Code_Start_Here||<---------------------------------||
  46. int dp[100001],wt[100001];
  47. int knapsack(int n,int w)
  48. {
  49.     memset(dp,0,sizeof(dp));
  50.  
  51.     for(int i=1;i<=n;i++)
  52.     {
  53.         for(int j=w;j>0;j--)
  54.         {
  55.             if(wt[i]<=j)
  56.             {
  57.                 dp[j]=max(dp[j],wt[i]+dp[j-wt[i]]);
  58.             }
  59.         }
  60.     }
  61.     return dp[w];
  62. }
  63. int main()
  64. {
  65.     //freopen("a.in", "r", stdin);
  66.     //freopen("a.out", "w", stdout);
  67.     int test,n;
  68.     cin>>test;
  69.     while(test--)
  70.     {
  71.         cin>>n;
  72.         int sum=0;
  73.         for(int i=1;i<=n;i++)
  74.         {
  75.             cin>>wt[i];
  76.             sum+=wt[i];
  77.         }
  78.  
  79.         cout<<sum-2*knapsack(n,sum/2)<<endl;
  80.     }
  81. }
Success #stdin #stdout 0s 4252KB
comments (?)
stdin
copy 
2
3
2 3 5
4
1 2 4 6
stdout
copy 
0
1
https://ideone.com/psT54b
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!