fork download
copy 
  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], mid;
  9. ll sum, ans;
  10.  
  11. map <ll, ll> v;
  12. void recur1(int pos, ll diff, ll sum)
  13. {
  14.     if (pos > mid)
  15.     {
  16.         v[diff] = max(v[diff], sum);
  17.         return;
  18.     }
  19.  
  20.     recur1(pos + 1, diff, sum);
  21.     recur1(pos + 1, diff + a[pos], sum + a[pos]);
  22.     recur1(pos + 1, abs(diff - a[pos]), sum + a[pos]);
  23. }
  24.  
  25. void recur2(int pos, ll diff, ll sum)
  26. {
  27.     if (pos > n)
  28.     {
  29.         if (v.find(diff) != v.end())
  30.             ans = max(ans, sum + v[diff]);
  31.         return;
  32.     }
  33.  
  34.     recur2(pos + 1, diff, sum);
  35.     recur2(pos + 1, diff + a[pos], sum + a[pos]);
  36.     recur2(pos + 1, abs(diff - a[pos]), sum + a[pos]);
  37. }
  38.  
  39. void sub2()
  40. {
  41.     v.clear();
  42.     mid = (n + 1) / 2;
  43.     recur1(1, 0, 0);
  44.     ans = 0;
  45.     recur2(mid + 1, 0, 0);
  46.     cout << sum - ans << endl;
  47. }
  48.  
  49. int main()
  50. {
  51.     ios::sync_with_stdio(false), cin.tie(nullptr);
  52.     #define name "test"
  53.     if (fopen(name".inp", "r"))
  54.     {
  55.         freopen(name".inp", "r", stdin);
  56.         freopen(name".out", "w", stdout);
  57.     }
  58.     while (cin >> n)
  59.     {
  60.         sum = 0;
  61.         for (int i = 1; i <= n; ++i)
  62.             cin >> a[i], sum += a[i];
  63.  
  64.         if (n <= 24) sub2();
  65.     }
  66. }
  67.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
3
1
2
3
4
2
2
4
1
stdout
copy 
0
1
https://ideone.com/9yiIKa
language:
C++14 (gcc 8.3)
created:
12 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!