fork download
copy 
  1. #include <bits/stdc++.h>  // Damn ....
  2. using namespace std;
  3. #define int long long
  4. #define all(v) v.begin(), v.end()
  5. #define rall(v) v.rbegin(),v.rend()
  6. #define pq_min priority_queue<int, vector<int>, greater<int>>
  7. typedef long long ll;
  8. typedef long double ld;
  9. const int MOD = 1e9 + 7;
  10. const ll OO = 2e18;
  11. const int oo = 1e9;
  12. const int sz = 1e5+5;
  13. ////////////////////////////////////////////////////////////////////////////////////////
  14. int n; int arr[105]; int dp[105][55555];
  15. int go(int i, int val) {
  16.     if (i >= n) return abs(val);;
  17.     if (dp[i][val] != -1)
  18.         return dp[i][val];
  19.     int a= go(i+1,val+arr[i]);
  20.     int b= go(i+1,val-arr[i]);
  21.     return dp[i][val] = min(a, b);
  22. }
  23. //////////////////////////////////////////////////////////////////////////////////////
  24. void _3OMDA() {
  25.     cin>>n;
  26.     for (int i = 0; i < n; i++) cin>>arr[i];
  27.     memset(dp,-1,sizeof(dp));
  28.     cout << go(0,0) << endl;
  29. }
  30. /////////////////////////////////////////////////////////////////////////////////////
  31. signed main() {
  32.     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  33.     //freopen("input.txt", "r", stdin);
  34.     //freopen("output.txt", "w", stdout);
  35.     int t = 1;
  36.     cin >> t;
  37.     for (int i = 0; i < t; i++) {
  38.         _3OMDA();
  39.     }
  40.     return 0;
  41. }
Success #stdin #stdout 0.02s 49244KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/9gSf2U
language:
C++ (gcc 8.3)
created:
11 hours 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!