fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define dd double
  5. #define ld long double
  6. #define ull unsigned long long
  7. #define yes cout << "YES\n"
  8. #define no cout << "NO\n"
  9. #define el "\n"
  10. #define Arwa ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  11. #define fix(x) cout << fixed << setprecision(x)
  12. #define all(v) v.begin(),v.end()
  13. #define dpp(v,val) memset(v,val,sizeof(v))
  14. #define mod 1e9+7
  15. const int N = 1e5 + 5;
  16. int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } // log(n) __gcd(a,b)
  17. //todo اى ويل بريبير ماى بيبرز تو بى ذا بيست ان زيس وورلد
  18. int n,sum;
  19. vector<int>v;
  20. int dp[101][50001];
  21. int rec(int i,int s1)
  22. {
  23.     if(i==n) 
  24.     {
  25.         return abs(s1-(sum-s1));
  26.         return 0;
  27.     }
  28.     if(dp[i][s1]!=-1) return dp[i][s1];
  29.     return dp[i][s1]=min(rec(i+1,s1+v[i]),rec(i+1,s1));
  30. }
  31. void HereWeGoAgain()
  32. {
  33.   cin>>n;
  34.   v.resize(n);
  35.   for(int i=0;i<n;i++) cin>>v[i];
  36.   for(int i=0;i<n;i++) sum+=v[i];
  37.   dpp(dp,-1);
  38.   cout<<rec(0,0)<<el;
  39. }
  40. int32_t main() 
  41. {
  42.     Arwa
  43.     int t=1;
  44.     cin>>t;
  45.     for(int i=1;i<=t;i++)
  46.     {
  47.     HereWeGoAgain();
  48.     }
  49.     return 0;
  50. }
Success #stdin #stdout 0.02s 43060KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/AH9Dmj
language:
C++ (gcc 8.3)
created:
2 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!