fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector< pair<int,int> > helper(vector<int> &a, int n) {
  5.     vector< pair<int,int> > ans(n);
  6.     ans[1] = {a[0], a[1]};
  7.     int fE = 0; //firstEnding -> the index at which the first part is ending
  8.  
  9.     for(int i=2; i<n; i++) {
  10.         ans[i] = ans[i-1];
  11.         //include the current element in the right part
  12.         ans[i].second += a[i];
  13.  
  14.         int cur = abs(ans[i].first - ans[i].second);
  15.         //expand the first part if it is profitable
  16.         while(fE+1 < i && abs(ans[i].first+a[fE+1]-(ans[i].second-a[fE+1])) < cur) {
  17.             fE++;
  18.             ans[i].first += a[fE];
  19.             ans[i].second -= a[fE];
  20.             cur = abs(ans[i].first - ans[i].second);
  21.         }
  22.     }
  23.  
  24.     return ans;
  25. }
  26.  
  27. int main() {
  28.     int n;
  29.     cin>>n;
  30.     vector<int> a(n);
  31.     for(int &x : a) cin>>x;
  32.  
  33.     vector< pair<int,int> > pref, suf;
  34.     pref = helper(a, n);
  35.     reverse(a.begin(), a.end());
  36.     suf = helper(a, n);
  37.     reverse(suf.begin(), suf.end());
  38.  
  39.     int ans = INT_MAX;
  40.     for(int i=1; i<n-2; i++) {
  41.         vector<int> temp{pref[i].first, pref[i].second, suf[i+1].first, suf[i+1].second};
  42.         sort(temp.begin(), temp.end());
  43.         ans = min(ans, abs(temp.front() - temp.back()));
  44.     }
  45.  
  46.     cout<<ans<<"\n";
  47. }
Success #stdin #stdout 0s 5584KB
comments (?)
stdin
copy 
10
10 71 84 33 6 47 23 25 52 64
stdout
copy 
36
https://ideone.com/XmJPQQ
language:
C++14 (gcc 8.3)
created:
2 years 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!