fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5. #define pii pair<int, int>
  6. #define pil pair<int, ll>
  7. #define pll pair<ll, ll>
  8. #define fi first
  9. #define se second
  10. #define vii vector<pair<int, int>>
  11. #define vil vector<pair<int, ll>>
  12. #define vll vector<pair<ll, ll>>
  13. #define vs vector<string>
  14. mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
  15. #define rand rd
  16. ll random(ll a, ll b) {
  17.     assert(a <= b);
  18.     return a + rd() % (b - a + 1);
  19. }
  20. int dx[] = {1, -1, 0, 0};
  21. int dy[] = {0, 0, 1, -1};
  22. const int MAXN = 1e5 + 5;
  23. const int INF = INT_MAX;
  24. const int MOD = 1e9 + 7;
  25. const ll INFLL = LLONG_MAX;
  26. int n, sum = 0;
  27. ll a[102];
  28.  
  29. namespace special {
  30.     ll calc() {
  31.         return min(a[2] - a[1], a[3] - a[2]);
  32.     }
  33. }
  34.  
  35. namespace sub1 {
  36.     ll calc() {
  37.         ll ans = INFLL;
  38.         ll tt = 1;
  39.         for (int i = 1; i <= n; i++) tt *= 3;
  40.         for (ll mask = 0; mask < tt; mask++) {
  41.             ll x = mask;
  42.             ll sa = 0, sc = 0;
  43.             int cntA = 0, cntB = 0, cntC = 0;
  44.             for (int i = 1; i <= n; i++) {
  45.                 int c = x % 3;
  46.                 x /= 3;
  47.                 if (c == 0) { 
  48.                     sa += a[i]; 
  49.                     cntA++; 
  50.                 }
  51.                 else if (c == 1) { 
  52.                     cntB++; 
  53.                 }
  54.                 else { 
  55.                     sc += a[i]; 
  56.                     cntC++; 
  57.                 }
  58.             }
  59.             if (cntA == 0 || cntB == 0 || cntC == 0) continue;
  60.             ans = min(ans, llabs(sa - sc));
  61.         }
  62.         return ans;
  63.     }
  64. }
  65.  
  66. namespace sub2 {
  67.     struct dl {
  68.         ll sum; int ca, cb, cc;
  69.     };
  70.     ll calc() {
  71.         int n1 = n / 2, n2 = n - n1;
  72.         ll t1 = 1, t2 = 1;
  73.         for (int i = 1; i <= n1; i++) t1 *= 3;
  74.         for (int i = 1; i <= n2; i++) t2 *= 3;
  75.         vector<dl> v1;
  76.         v1.reserve(t1);
  77.         vector<ll> v2[8];
  78.         for (int mask = 0; mask < t1; mask++) {
  79.             ll x = mask, sa = 0, sc = 0; int ca = 0, cc = 0;
  80.             for (int i = 1; i <= n1; i++) {
  81.                 int c = x % 3; x /= 3;
  82.                 if (c == 0) {
  83.                     sa += a[i];
  84.                     ca++;
  85.                 }
  86.                 else if (c == 2) {
  87.                     sc += a[i];
  88.                     cc++;
  89.                 }
  90.             }
  91.             int cb = n1 - ca - cc;
  92.             v1.push_back({sa - sc, ca, cb, cc});
  93.         }
  94.         for (int mask = 0; mask < t2; mask++) {
  95.             ll x = mask, sa = 0, sc = 0; int ca = 0, cc = 0;
  96.             for (int i = 1; i <= n2; i++) {
  97.                 int c = x % 3; x /= 3;
  98.                 if (c == 0) {
  99.                     sa += a[n1 + i];
  100.                     ca++;
  101.                 }
  102.                 else if (c == 2) {
  103.                     sc += a[n1 + i];
  104.                     cc++;
  105.                 }
  106.             }
  107.             int cb = n2 - ca - cc;
  108.             ll di = sa - sc;
  109.             int c1 = ca > 0, c2 = cb > 0, c3 = cc > 0;
  110. int idx = (c1 << 2) | (c2 << 1) | c3;
  111.             v2[idx].push_back(di);
  112.         }
  113.         for (auto &v : v2) sort(v.begin(), v.end());
  114.         ll ans = INFLL;
  115.         for (auto &t : v1) {
  116.             ll d1 = t.sum; ll ca = t.ca; ll cb = t.cb; ll cc = t.cc;
  117.             for (int idx = 0; idx < 8; idx++) {
  118.                 int c1 = idx >> 2;
  119.                 int c2 = (idx >> 1) & 1;
  120.                 int c3 = idx & 1;
  121.                 if ((ca > 0 || c1) && (cb > 0 || c2) && (cc > 0 || c3)) {
  122.                     auto &v = v2[idx];
  123.                     if (v.empty()) continue;
  124.                     auto it = lower_bound(v.begin(), v.end(), -d1);
  125.                     if (it != v.end()) {
  126.                         ans = min(ans, llabs(d1 + *it));
  127.                     }
  128.                     if (it != v.begin()) {
  129.                         it--;
  130.                         ans = min(ans, llabs(d1 + *it));
  131.                     }
  132.                 }
  133.             }
  134.         }
  135.         return ans;
  136.     }
  137. }
  138.  
  139. namespace sub3 {
  140.     const int MAXS = 2e3 + 33;
  141.     ll calc() {
  142.         for (int i = 1; i <= n; i++) {
  143.             sum += a[i];
  144.         }
  145.         int s1 = 2 * sum + 1, s2 = sum;
  146.         bitset<8> pv[MAXS], cur[MAXS];
  147.         for (int i = 0; i < s1; i++) pv[i].reset();
  148.         pv[s2].set(0);
  149.         for (int i = 1; i <= n; i++) {
  150.             for (int j = 0; j < s1; j++) {
  151.                 cur[j].reset();
  152.             }
  153.             int v = a[i];
  154.             for (int j = 0; j < s1; j++) {
  155.                 for (int m = 0; m < 8; m++) {
  156.                     if (!pv[j].test(m)) continue;
  157.                     int nm;
  158.                     nm = m | 1;
  159.                     if (j + v < s1) cur[j + v].set(nm);
  160.                     nm = m | 2;
  161.                     cur[j].set(nm);
  162.                     nm = m | 4;
  163.                     if (j >= v) cur[j - v].set(nm);
  164.  
  165.                 }
  166.             }
  167.         }
  168.         swap(pv, cur);
  169.         ll ans = INFLL;
  170.         for (int j = 0; j < s1; j++) {
  171.             if (pv[j].test(7)) {
  172.                 ll d = llabs(j - s2);
  173.                 if (d < ans) ans = d;
  174.             }
  175.         }
  176.         return ans;
  177.     }
  178. }
  179.  
  180.  
  181. signed main() {
  182.  
  183. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pGdhNP
language:
C++14 (clang 8.0)
created:
10 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!