提出 #7343284

---

ソースコード 拡げる

#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
template<class S, class T> inline S min_L(S a,T b){
  return a<=b?a:b;
}
template<class S, class T> inline S max_L(S a,T b){
  return a>=b?a:b;
}
template<class T> void malloc1d(T **arr, int x){
  (*arr) = (T*)malloc(x*sizeof(T));
}
template<class T> void free1d(T *arr){
  free(arr);
}
inline void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void rd(long long &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(long long x){
  char f[20];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
template<class S, class T> inline S chmin(S &a, T b){
  if(a>b){
    a=b;
  }
  return a;
}
template<class T> struct Grid1d{
  T *d, *d_s;
  int *dw, *lf, n, *rg, set_d, set_s, *up;
  void malloc(const int nn){
    n = nn;
    set_s = 0;
    set_d = 0;
    malloc1d(&d, n);
  }
  void free(void){
    free1d(d);
    if(set_s){
      free1d(d_s);
    }
    if(set_d){
      free1d(up);
      free1d(dw);
    }
  }
  T& operator[](int a){
    return d[a];
  }
  void setSum(void){
    int i;
    if(set_s == 0){
      set_s = 1;
      malloc1d(&d_s, n+1);
    }
    d_s[0] = 0;
    for(i=0;i<(n);i++){
      d_s[i+1] = d_s[i] + d[i];
    }
  }
  void setDir(void){
    int i;
    if(set_d == 0){
      set_d = 1;
      malloc1d(&up, n);
      malloc1d(&dw, n);
      lf = dw;
      rg = up;
    }
    lf[0] = 1;
    for(i=(1);i<(n);i++){
      if(d[i]==d[i-1]){
        lf[i] = 1 + lf[i-1];
      }
      else{
        lf[i] = 1 ;
      }
    }
    rg[n-1] = 1;
    for(i=n-2;i>=0;i--){
      if(d[i]==d[i+1]){
        rg[i] = 1 + rg[i+1];
      }
      else{
        rg[i] = 1 ;
      }
    }
  }
  void setDirMatch(const T v){
    int i;
    if(set_d == 0){
      set_d = 1;
      malloc1d(&up, n);
      malloc1d(&dw, n);
      lf = dw;
      rg = up;
    }
    if(d[0]==v){
      lf[0] =1;
    }
    else{
      lf[0] =0;
    }
    for(i=(1);i<(n);i++){
      if(d[i]==v){
        lf[i] =1 + lf[i-1];
      }
      else{
        lf[i] =0;
      }
    }
    if(d[n-1]==v){
      rg[n-1] =1;
    }
    else{
      rg[n-1] =0;
    }
    for(i=n-2;i>=0;i--){
      if(d[i]==v){
        rg[i] =1 + rg[i+1];
      }
      else{
        rg[i] =0;
      }
    }
  }
  inline T getSum(const int a, const int b){
    return d_s[b+1] - d_s[a];
  }
}
;
int N;
Grid1d<long long> A;
int main(){
  int i, j, k, x, y;
  long long a, b, c, d, res=4611686016279904256LL;
  rd(N);
  A.malloc(N+1);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=0;Lj4PdHRW<(N);Lj4PdHRW++){
      rd(A[Lj4PdHRW]);
    }
  }
  A.setSum();
  x = y = 0;
  for(i=0;i<(N);i++){
    while(x+1 < N && A.getSum(x+1,i) >= A.getSum(0,x)){
      x++;
    }
    while(y+1 < N && A.getSum(y+1,N-1) >= A.getSum(i+1,y)){
      y++;
    }
    for(j=0;j<(2);j++){
      for(k=0;k<(2);k++){
        a = A.getSum(0,x-1+j);
        b = A.getSum(x+j,i);
        c = A.getSum(i+1,y-1+k);
        d = A.getSum(y+k,N-1);
        chmin(res, max_L(max_L(max_L(a, b), c), d)-min_L(min_L(min_L(a, b), c), d));
      }
    }
  }
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20190902-1

// --- original code ---
// int N;
// Grid1d<ll> A;
// {
//   int i, j, k, x, y;
//   ll a, b, c, d;
//   ll res = ll_inf;
// 
//   rd(N);
//   A.malloc(N+1);
//   rd(A(N));
//   A.setSum();
// 
//   x = y = 0;
//   rep(i,N){
//     while(x+1 < N && A.getSum(x+1,i) >= A.getSum(0,x)) x++;
//     while(y+1 < N && A.getSum(y+1,N-1) >= A.getSum(i+1,y)) y++;
//     rep(j,2) rep(k,2){
//       a = A.getSum(0,x-1+j);
//       b = A.getSum(x+j,i);
//       c = A.getSum(i+1,y-1+k);
//       d = A.getSum(y+k,N-1);
//       res <?= max(a,b,c,d) - min(a,b,c,d);
//     }
//   }
// 
//   wt(res);
// }

提出情報

ジャッジ結果