fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long 
  4.  
  5. int n, sum, a[10000 + 97]; 
  6.  
  7. void sub1(){ 
  8.  
  9.     int ans = LLONG_MAX;
  10.  
  11.     for(int i = 1; i < 1 << n; i++){ 
  12.  
  13.         int res = 0;
  14.         for(int j = 0; j < n; j++)
  15.             if (i >> j & 1)
  16.                 res += a[j]; 
  17.  
  18.         if (res << 1 <= sum)
  19.             ans = min(ans, sum - (res << 1)); 
  20.  
  21.     }
  22.  
  23.     cout << ans;
  24. } 
  25.  
  26. void sub2(){ 
  27.  
  28.     vector <bool> dp((sum >> 1) + 1);
  29.  
  30.     dp[0] = true;
  31.     for(int i = 0; i < n; i++)
  32.         for(int j = sum >> 1; j >= a[i]; j--)
  33.             dp[j] = dp[j] || dp[j - a[i]]; 
  34.  
  35.     for(int i = sum >> 1; i >= 0; i--)
  36.         if (dp[i]){
  37.             cout << sum - (i << 1);
  38.             return;
  39.         } 
  40.  
  41. }
  42. void sub3(){
  43.     int ans = LLONG_MAX; 
  44.  
  45.     int m = n >> 1; // 0 -> mid
  46.     vector <int> tmp(1 << m); 
  47.  
  48.     for(int i = 1; i < 1 << m; i++)
  49.         for(int j = 0; j < m; j++)
  50.             if (i >> j & 1)
  51.                 tmp[i] += a[j]; 
  52.  
  53.     sort(tmp.begin(), tmp.end());
  54.     n -= m; // mid -> n 
  55.  
  56.     for(int i = 1; i < 1 << n; i++){ 
  57.  
  58.         int res = 0;
  59.         for(int j = 0; j < n; j++)
  60.             if (i >> j & 1)
  61.                 res += a[j + m]; 
  62.  
  63.         int id = upper_bound(tmp.begin(), tmp.end(), (sum >> 1) - res) - tmp.begin();
  64.         if (id > 0)
  65.             ans = min(ans, sum - ((res + tmp[id - 1]) << 1));
  66.  
  67.     }
  68.  
  69.     cout << ans; 
  70.  
  71. }
  72. void sub4(){ 
  73.  
  74.     bitset <600000 + 97> dp; 
  75.  
  76.     dp[0] = true;
  77.     for(int i = 0; i < n; i++)
  78.         dp |= dp << a[i]; 
  79.  
  80.     for(int i = sum >> 1; i >= 0; i--)
  81.         if (dp[i]){
  82.             cout << sum - (i << 1);
  83.             return;
  84.         } 
  85.  
  86. }
  87. signed main(){ 
  88.  
  89.     freopen("candy.inp", "r", stdin);
  90.     freopen("candy.out", "w", stdout); 
  91.  
  92.     ios_base::sync_with_stdio(NULL);
  93.     cin.tie(NULL); cin.tie(NULL);  
  94.  
  95.     cin >> n;
  96.     for(int i = 0; i < n; i++){
  97.         cin >> a[i];
  98.         sum += a[i];
  99.     } 
  100.  
  101.     if (n <= 20) sub1(); else
  102.         if (n <= 40) sub3(); else
  103.             if (n <= 1e3) sub2(); else sub4();
  104.  
  105. }
  106.  
Success #stdin #stdout 0.01s 5548KB
comments (?)
stdin
copy 
5
19 17 13 9 7
stdout
copy 
Standard output is empty
https://ideone.com/o7NeF5
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
secret

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!