Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #include<string.h>
- #include<math.h>
- #include<ctype.h>
- #include<stdlib.h>
- #include<cstdio>
- #include<cstring>
- #include<string>
- #include<cmath>
- #include<iostream>
- #include<cctype>
- #include<map>
- #include<stack>
- #include<cstdlib>
- #include<queue>
- #include<vector>
- #include<algorithm>
- #include<bitset>
- #include<algorithm>
- #include<set>
- #include<limits.h>
- #include <sstream>
- using namespace std;
- typedef long int LD;
- typedef long long int LLD;
- typedef float F;
- typedef double LF;
- typedef unsigned int U;
- typedef unsigned long int LU;
- typedef unsigned long long int LLU;
- typedef char C;
- /*----------simple input section ------------ */
- #define sf scanf
- #define sfi(x) scanf("%d",&x)
- #define sfc(x) scanf("%c",&x)
- #define sfi2(x,y) scanf("%d%d",&x,&y)
- #define sfll2(x,y) scanf("%lld%lld",&x,&y)
- #define sfu2(x,y) scanf("%llu%llu",&x,&y)
- #define sfl(x) scanf("%ld",&x)
- #define sfll(x) scanf("%lld",&x)
- #define sfd(x) scanf("%lf",&x)
- #define sfu(x) scanf("%llu",&x)
- #define sfs(x) scanf("%s",x)
- /*----------simple input section ------------ */
- #define pf printf
- #define pfi(x) printf("%d\n",x)
- #define pfl(x) printf("%ld\n",x)
- #define pfll(x) printf("%lld\n",x)
- #define pfu(x) printf("%llu\n",x)
- #define pfs(x) printf("%s\n",x)
- #define pfc(x) printf("%c\n",x)
- #define pfd(x) printf("%lf\n",x)
- /*----------file input section ------------ */
- #define f_input freopen("input.txt","r",stdin);
- #define f_output freopen("output.txt","w",stdout);
- #define pb(x) push_back(x)
- #define PI acos(-1.0)
- #define sq(x) (x)*(x)
- #define mem(x,y) memset(x,y,sizeof(x))
- #define TEST int cs,T;sfi(T);getchar();for(cs=1;cs<=T;cs++)
- #define nn printf("\n")
- // xx-> diagonal -> 8 horizontal/vertical->4
- const int xx[] = {0, 1, 0, -1, -1, 1, -1, 1};
- const int yy[] = {1, 0, -1, 0, 1, 1, -1, -1};
- // KX-> Knight moves
- const int kx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
- const int ky[] = {1, 2, 2, 1, -1, -2, -2, -1};
- /******** debug **********/
- #define chk1 printf("hi......1 \n")
- #define chk2 printf("hi......2 \n")
- #define mod 1000000007
- #define eps 10e-8
- #define sz 100004
- #define sz1 102
- #define sz2 5
- /******* start my code ********/
- int arr[sz1];
- int knap(int i,int n,int sum,int limit)
- {
- if(i==n)
- {
- return sum;
- }
- int q1,q2;
- q1=q2=0;
- if(sum+arr[i]<=limit)
- q1=knap(i+1,n,sum+arr[i],limit);
- if(sum<=limit)
- q2=knap(i+1,n,sum,limit);
- return max(q1,q2);
- }
- int main()
- {
- int i,j,k,n,m,sum;
- TEST /// taking input number of test case and run it.......
- {
- sfi(n);
- sum=0;
- for(i=0; i<n; i++)
- {
- sfi(arr[i]);
- sum+=arr[i];
- }
- int ans = knap(0,n,0,(sum+1)/2);
- pfi(abs((sum-ans)-ans));
- }
- return 0;
- }
- /*
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement