fork download
copy 
  1. //author divesh uttamchandani
  2. //EQGIFTS
  3. //logic sorted the difference of pairs as it is the one which matters now problem reduces to assigning +ve
  4. //negetive signs such that the sum is as close to zero or divide the differences in two sets +ve/-ve such
  5. //the sum of +ve parts is closest to sum of negetive parts
  6.  
  7. #include<bits/stdc++.h>
  8. using namespace std;
  9.  
  10. typedef vector<int> vi;
  11. typedef vector<vi> vvi;
  12. typedef pair<int,int> ii;
  13. typedef long long int lli;
  14. #define loop(i,t) for(i=0;i<t;++i)
  15. #define sz(a) int((a).size())
  16. #define pb push_back
  17. #define all(c) (c).begin(),(c).end()
  18. #define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
  19. #define present(c,x) ((c).find(x) != (c).end())
  20. #define cpresent(c,x) (find(all(c),x) != (c).end())
  21. int N,i,s=0,s1,A,B;
  22. vector<int> dp(23000,-1);  //dp[i] contains the max sum attainable up to i;
  23. vector<int> v;             //contains the sorted elements
  24.  
  25. int solve(int i)    //gives sum attainable upto i
  26. {
  27.     if(i==0)
  28.         return 0;
  29.  
  30.     if (dp[i]==-1)
  31.     {
  32.         int j;
  33.         for(j=0;v[j]<=i;j++)    //first iterate over the eligible elements from the array;
  34.         {
  35.             dp[i]=max((solve(i-v[j])+v[j]),dp[i]);
  36.         }
  37.     }
  38.         return dp[i];
  39. }
  40.  
  41. int main()
  42. {
  43.     dp[0]=0;
  44.     cin>>N;
  45.     loop(i,N)
  46.     {
  47.         cin>>A>>B;
  48.         if(A!=B)
  49.         v.pb(abs(A-B));
  50.         s+=abs(A-B);
  51.     }
  52.     sort(all(v));
  53.     s1=s/2; //this is the required sum;
  54.     cout<<abs(s-solve(s1)-s1);
  55. 	return 0;
  56. }
Success #stdin #stdout 0s 3476KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mEhrsQ
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!