fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define fir first
  4. #define sec second
  5. #define pll pair <ll, ll>
  6. #define sz(x) (int)x.size()
  7. #define all(v) v.begin(), v.end()
  8. #define pushb push_back
  9. using namespace std;
  10. const int N = 96;
  11.  
  12. int n, a[N + 5], mid;
  13. ll sum, ans;
  14. unordered_map <ll, ll> dp, dp0;
  15.  
  16. void sub4()
  17. {
  18.     dp.clear(); dp0.clear();
  19.     dp[0] = 0, dp0[0] = 0;
  20.     for (int i = 1; i <= n; ++i)
  21.     {
  22.         for (const pair <ll, ll> &tmp : dp)
  23.         {
  24.             dp0[tmp.fir + a[i]] = max(dp0[tmp.fir + a[i]], tmp.sec + a[i]);
  25.             dp0[abs(tmp.fir - a[i])] = max(dp0[abs(tmp.fir - a[i])], tmp.sec + a[i]);
  26.         }
  27.  
  28.         for (const pair <ll, ll> &tmp : dp0)
  29.             dp[tmp.fir] = tmp.sec;
  30.     }
  31.  
  32.     cout << sum - dp0[0] << endl;
  33. }
  34.  
  35. //map <ll, ll> v;
  36. vector <pll> v;
  37. vector <pll> real_v;
  38.  
  39. void recur1(int pos, ll diff, ll curr)
  40. {
  41.     if (pos > mid)
  42.     {
  43.         v.pushb({diff, curr});
  44.         return;
  45.     }
  46.  
  47.     recur1(pos + 1, diff, curr);
  48.     recur1(pos + 1, diff + a[pos], curr + a[pos]);
  49.     recur1(pos + 1, abs(diff - a[pos]), curr + a[pos]);
  50. }
  51.  
  52. void recur2(int pos, ll diff, ll curr)
  53. {
  54.     if (pos > n)
  55.     {
  56.         int ind = lower_bound(all(v), pll(diff, 0)) - v.begin();
  57.         if (ind >= sz(v) || v[ind].fir != diff) return;
  58.         ans = max(ans, curr + v[ind].sec);
  59.         return;
  60.     }
  61.  
  62.     recur2(pos + 1, diff, curr);
  63.     recur2(pos + 1, diff + a[pos], curr + a[pos]);
  64.     recur2(pos + 1, abs(diff - a[pos]), curr + a[pos]);
  65. }
  66.  
  67. void sub2()
  68. {
  69.     v.clear();
  70.     real_v.clear();
  71.     mid = (n + 1) / 2;
  72.     recur1(1, 0, 0);
  73.     sort(all(v));
  74.     real_v.pushb(v[0]);
  75.     for (int i = 1; i < sz(v); ++i)
  76.     {
  77.         if (v[i].fir == real_v.back().fir)
  78.             real_v.pop_back();
  79.         real_v.pushb(v[i]);
  80.     }
  81.     swap(v, real_v);
  82.     ans = 0;
  83.     recur2(mid + 1, 0, 0);
  84.     cout << sum - ans << endl;
  85. }
  86.  
  87. int main()
  88. {
  89.     ios::sync_with_stdio(false), cin.tie(nullptr);
  90.     #define name "treasure"
  91.     if (fopen(name".inp", "r"))
  92.     {
  93.         freopen(name".inp", "r", stdin);
  94.         freopen(name".out", "w", stdout);
  95.     }
  96.     while (cin >> n)
  97.     {
  98.         sum = 0;
  99.         for (int i = 1; i <= n; ++i)
  100.             cin >> a[i], sum += a[i];
  101.  
  102.         if (n <= 24) sub2();
  103.         else sub4();
  104.     }
  105. }
  106.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin 
3
1
2
3
4
2
2
4
1
stdout 
0
1
https://ideone.com/iMyF0G
language:
C++14 (gcc 8.3)
created:
6 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!