fork download 
  1. // Author : hynu
  2. // Problem : 
  3.  
  4. #pragma GCC optimize("O3,unroll-loops")
  5. #include <bits/stdc++.h>
  6.  
  7. #if LOCAL
  8. #include "algo/debug.h"
  9. #endif
  10.  
  11. using namespace std;
  12. using ll = long long;
  13.  
  14. const int MOD = 1e9 + 7;
  15. const int LIMIT = 1e6 + 7;
  16. const ll INF = INT_MAX;
  17.  
  18. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  19.  
  20. int n;
  21. vector<int> arr;
  22.  
  23. namespace subtask1 {    
  24.     int res = INF;
  25.     void backtrack(int p, ll a, ll b, ll c) {
  26.         if (p == n) {
  27.             res = min(res, (int)(max({a, b, c}) - min({a, b, c})));
  28.             return;
  29.         }
  30.  
  31.         backtrack(p + 1, a + arr[p], b, c);
  32.         backtrack(p + 1, a, b + arr[p], c);
  33.         backtrack(p + 1, a, b, c + arr[p]);
  34.     }
  35.  
  36.     int solve() {
  37.         backtrack(0, 0, 0, 0);
  38.         return res;
  39.     }
  40. }
  41.  
  42. namespace subtask2 {    
  43.     void gen(int l, int r, vector<array<ll, 3>>& vals) {
  44.         int len = r - l;
  45.  
  46.         int total = 1;
  47.         for (int i = 0; i < len; i++) total *= 3;
  48.  
  49.         for (int mask = 0; mask < total; ++mask) {
  50.             int m = mask;
  51.             ll a, b, c;
  52.             a = b = c = 0;
  53.  
  54.             for (int i = 0; i < len; ++i) {
  55.                 int r = m % 3;
  56.                 m /= 3;
  57.  
  58.                 int val = arr[l + i];
  59.                 if (r == 0) a += val;
  60.                 if (r == 1) b += val;
  61.                 if (r == 2) c += val;
  62.             }
  63.             vals.push_back({a, b, c});
  64.         }
  65.     }
  66.  
  67.  
  68.     void prune(vector<array<ll, 3>>& vals) {
  69.         sort(vals.begin(), vals.end(), [](auto &x, auto &y) {
  70.             if (x[0] != y[0]) return x[0] < y[0];
  71.             if (x[1] != y[1]) return x[1] < y[1];
  72.             return x[2] < y[2];
  73.         });
  74.  
  75.         map<ll, ll> front;
  76.         vector<array<ll, 3>> res;
  77.  
  78.         for (auto [a, b, c] : vals) {
  79.             auto it = front.lower_bound(b);
  80.             bool found = false;
  81.  
  82.             if (it != front.begin()) {
  83.                 --it;
  84.                 if (it->second <= c) found = true;
  85.             }
  86.  
  87.             if (found) continue;
  88.  
  89.             while (it != front.end() && it->second >= c) it = front.erase(it);
  90.  
  91.             front[b] = c;
  92.             res.push_back({a, b, c});
  93.         }
  94.  
  95.         vals = res;
  96.         return;
  97.     }
  98.  
  99.     ll solve() {
  100.         int res = INF;
  101.         vector<array<ll, 3>> v1, v2;
  102.  
  103.         gen(0, n >> 1, v1);
  104.         gen(n >> 1, n, v2);
  105.         prune(v1); 
  106.         prune(v2);
  107.  
  108.         for (auto [a1, b1, c1] : v1) {
  109.             for (auto [a2, b2, c2] : v2) {
  110.                 ll a = a1 + a2;
  111.                 ll b = b1 + b2;
  112.                 ll c = c1 + c2;
  113.  
  114.                 res = min(res, (int)(max({a, b, c}) - min({a, b, c})));
  115.             }
  116.         }
  117.  
  118.         return res;  
  119.     }
  120. }
  121.  
  122. namespace subtask3 {
  123.     //dp
  124. }
  125.  
  126.  
  127.  
  128. class stress {
  129. private: 
  130.     int rnd(int l, int r) {
  131.         return uniform_int_distribution<int>(l, r)(rng);
  132.     }
  133. public:
  134.     stress(int t, int n) {
  135.         bool accept = true;
  136.         while (t--) {
  137.             arr.assign(n, 0);
  138.             for (int& val : arr) val = rnd(1, 1e6);
  139.  
  140.             int res1 = subtask1::solve();
  141.             int res2 = subtask1::solve();
  142.  
  143.             if (res1 != res2) {
  144.                 cout << n << '\n';
  145.                 for (int val : arr) cout << val << ' ';
  146.                 accept = false;
  147.                 return;
  148.             }
  149.         }
  150.         if (accept) cout << "passed!";
  151.     }
  152. };
  153.  
  154. signed main() { 
  155.     cin.tie(nullptr), cout.tie(nullptr) -> ios_base::sync_with_stdio(false);
  156.  
  157.     #define task "sol"
  158.     if (fopen(task".inp", "r")) {
  159.         freopen(task".inp", "r", stdin), freopen(task".out", "w", stdout);
  160.     }
  161.  
  162.     /*
  163.     cin >> n;
  164.     arr.resize(n);
  165.  
  166.     for (int& val : arr) cin >> val;
  167.  
  168.     subtask2::solve();
  169.     */
  170.  
  171.     int t;
  172.     cin >> t;
  173.  
  174.     stress(t, 10);
  175.  
  176.     return 0;
  177. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
passed!
https://ideone.com/J6fMtl
language:
C++14 (clang 8.0)
created:
13 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!