Submission #5913161
Source Code Expand
/***********************************************************
*This code By @1353055672(Ligen) *
*[Warning]You're not excepted to understand this code! *
*NOIP 2019 RP++ *
***********************************************************/
//#pragma GCC optimize(3)
#define ADD_STACK int size = 512 << 20;\
char *pp = (char*)malloc(size) + size; \
__asm__("movl %0, %%esp\n" :: "r"(pp))
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include<ctime>
#include<vector>
#define ll long long
#define ull unsigned long long
#define mn 200020
#define Max(x,y) ((x>y)?x:y)
#define Min(x,y) ((x<y)?x:y)
#define Abs(x) (((x)<(0))?(-(x)):(x))
#define infll (ll)(1e18)
#define infint (1<<30)
#define mod (int)(1e9+7)
#define FOR(a,b,c) for (register int a=b;a<=c;++a)
#define FORD(a,b,c) for (register int a=b;a>=c;--a)
using namespace std;
//char buf[1<<20],*p1=buf,*p2=buf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline ll read(){
ll x=0,f=1;char c;
for(c=getchar();c<'0'||c>'9';f=((c=='-')?-1:f),c=getchar());
for(;c>='0'&&c<='9';x=x*10+c-'0',c=getchar());return x*f;
}
template<typename T>
inline void write(T a){
if(a==0){putchar('0');return;}if(a<0)putchar('-'),a=-a;char c1[120];int h=0;
while(a)c1[++h]=a%10+'0',a/=10;FORD(i,h,1)putchar(c1[i]);
}
inline void write_(){return;}
template<typename T,typename... Args>
inline void write_(T a,Args... b){write(a);putchar(' ');write_(b...);}
inline void writeln(){putchar('\n');return;}
template<typename T,typename... Args>
inline void writeln(T a,Args... b){write(a);putchar(' ');writeln(b...);}
//need c++11
//inline void write(ll a){
// if(a==0){putchar('0');return;}if(a<0)putchar('-'),a=-a;char c1[120];int h=0;
// while(a)c1[++h]=a%10+'0',a/=10;FORD(i,h,1)putchar(c1[i]);
//}
//inline void write_(ll a){write(a);putchar(' ');}
//inline void writeln(ll a){write(a);putchar('\n');}
inline ll gcd(ll a,ll b){return a==0?b:gcd(b%a,a);}
inline ll lcm(ll a,ll b){return 1ll*a/gcd(a,b)*b;}
inline ll Pow(ll n,ll a){ll b=1;while(a){if(a&1)b=1ll*b*n%mod;n=1ll*n*n%mod;a>>=1;}return b;}
//---------------------Head Files--------------------------//
ll n,a[mn],x1,x2,x3;
ll sum[mn],ans;
signed main(){
#ifdef _WIN32
freopen("0.in","r",stdin);
// freopen("0.out","w",stdout);
// ADD_STACK;
long double be=clock();
#endif
n=read();
FOR(i,1,n)a[i]=read(),sum[i]=sum[i-1]+a[i];
x2=2;
FOR(i,3,n-1)if(Abs(sum[n]-2ll*sum[x2])>=Abs(sum[n]-2ll*sum[i]))x2=i;
ll xx=x2;
ans=infll;
#define N 10
for(x2=Max(2,xx-N);x2<=Min(n-1,xx+N);++x2){
x1=1;
FOR(i,2,x2-1)if(Abs(sum[x2]-2ll*sum[x1])>=Abs(sum[x2]-2ll*sum[i]))x1=i;
ll xx1=x1;
for(x1=Max(1,xx1-N);x1<=Min(x2-1,xx1+N);++x1){
x3=x2+1;
FOR(i,x2+1,n)if(Abs(sum[n]+sum[x2]-2ll*sum[x3])>=Abs(sum[n]+sum[x2]-2ll*sum[i]))x3=i;
ll xx3=x3;
for(x3=Max(x2+1,xx3-N);x3<=Min(n,xx3+N);++x3){
ll a=sum[x1],b=sum[x2]-sum[x1],c=sum[x3]-sum[x2],d=sum[n]-sum[x3];
ans=Min(ans,Max(Max(a,b),Max(c,d))-Min(Min(a,b),Min(c,d)));
}
// writeln(x1,x2,x3);
}
}
writeln(ans);
#ifdef _WIN32
long double en=clock();
printf("Time: %.0Lfms\n",en-be);
fclose(stdin);fclose(stdout);
#endif
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Equal Cut |
User |
ligen131 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3602 Byte |
Status |
WA |
Exec Time |
373 ms |
Memory |
3328 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 600 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
subtask_1_01.txt |
AC |
1 ms |
256 KB |
subtask_1_02.txt |
AC |
205 ms |
3072 KB |
subtask_1_03.txt |
AC |
95 ms |
1536 KB |
subtask_1_04.txt |
AC |
143 ms |
2176 KB |
subtask_1_05.txt |
AC |
1 ms |
256 KB |
subtask_1_06.txt |
WA |
10 ms |
640 KB |
subtask_1_07.txt |
AC |
126 ms |
2048 KB |
subtask_1_08.txt |
WA |
63 ms |
1408 KB |
subtask_1_09.txt |
AC |
122 ms |
2048 KB |
subtask_1_10.txt |
WA |
156 ms |
2688 KB |
subtask_1_11.txt |
AC |
177 ms |
3072 KB |
subtask_1_12.txt |
AC |
10 ms |
1664 KB |
subtask_1_13.txt |
AC |
121 ms |
2176 KB |
subtask_1_14.txt |
AC |
17 ms |
896 KB |
subtask_1_15.txt |
AC |
28 ms |
640 KB |
subtask_1_16.txt |
WA |
35 ms |
1920 KB |
subtask_1_17.txt |
WA |
24 ms |
1664 KB |
subtask_1_18.txt |
WA |
2 ms |
384 KB |
subtask_1_19.txt |
AC |
112 ms |
3200 KB |
subtask_1_20.txt |
AC |
209 ms |
3072 KB |
subtask_1_21.txt |
AC |
107 ms |
1792 KB |
subtask_1_22.txt |
AC |
71 ms |
1152 KB |
subtask_1_23.txt |
AC |
180 ms |
2816 KB |
subtask_1_24.txt |
WA |
71 ms |
3328 KB |
subtask_1_25.txt |
WA |
192 ms |
3328 KB |
subtask_1_26.txt |
WA |
71 ms |
3328 KB |
subtask_1_27.txt |
WA |
184 ms |
3328 KB |
subtask_1_28.txt |
AC |
82 ms |
3328 KB |
subtask_1_29.txt |
WA |
345 ms |
3328 KB |
subtask_1_30.txt |
AC |
180 ms |
3328 KB |
subtask_1_31.txt |
WA |
318 ms |
3328 KB |
subtask_1_32.txt |
AC |
373 ms |
3328 KB |
subtask_1_33.txt |
AC |
318 ms |
3328 KB |
subtask_1_34.txt |
WA |
67 ms |
3328 KB |
subtask_1_35.txt |
AC |
182 ms |
3328 KB |
subtask_1_36.txt |
WA |
16 ms |
3328 KB |
subtask_1_37.txt |
AC |
287 ms |
3328 KB |