fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define fir first
  4. #define sec second
  5. using namespace std;
  6. const int N = 96;
  7.  
  8. int n, a[N + 5];
  9. ll sum;
  10. unordered_map <ll, ll> dp, dp0;
  11. int main()
  12. {
  13.     ios::sync_with_stdio(false), cin.tie(nullptr);
  14.     #define name "treasure"
  15.     if (fopen(name".inp", "r"))
  16.     {
  17.         freopen(name".inp", "r", stdin);
  18.         freopen(name".out", "w", stdout);
  19.     }
  20.     while (cin >> n)
  21.     {
  22.         sum = 0;
  23.         for (int i = 1; i <= n; ++i)
  24.             cin >> a[i], sum += a[i];
  25.  
  26.         dp.clear(); dp0.clear();
  27.         dp[0] = 0, dp0[0] = 0;
  28.         for (int i = 1; i <= n; ++i)
  29.         {
  30.             for (const pair <ll, ll> &tmp : dp)
  31.             {
  32.                 dp0[tmp.fir + a[i]] = max(dp0[tmp.fir + a[i]], tmp.sec + a[i]);
  33.                 dp0[abs(tmp.fir - a[i])] = max(dp0[abs(tmp.fir - a[i])], tmp.sec + a[i]);
  34.             }
  35.  
  36.             for (const pair <ll, ll> &tmp : dp0)
  37.                 dp[tmp.fir] = tmp.sec;
  38.         }
  39.  
  40.         cout << sum - dp0[0] << endl;
  41.     }
  42. }
  43.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
4
2
2
4
1
3
1
2
3
stdout 
1
0
https://ideone.com/93mr0E
language:
C++14 (gcc 8.3)
created:
7 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!