Submission #5913175


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 100
    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 3603 Byte
Status WA
Exec Time 2103 ms
Memory 3328 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
AC × 3
AC × 10
WA × 4
TLE × 29
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 TLE 2103 ms 3072 KB
subtask_1_03.txt TLE 2103 ms 1536 KB
subtask_1_04.txt TLE 2103 ms 2176 KB
subtask_1_05.txt AC 11 ms 256 KB
subtask_1_06.txt WA 579 ms 640 KB
subtask_1_07.txt TLE 2103 ms 2048 KB
subtask_1_08.txt TLE 2103 ms 1408 KB
subtask_1_09.txt TLE 2103 ms 1920 KB
subtask_1_10.txt TLE 2103 ms 2688 KB
subtask_1_11.txt TLE 2103 ms 2944 KB
subtask_1_12.txt AC 48 ms 1664 KB
subtask_1_13.txt TLE 2103 ms 2176 KB
subtask_1_14.txt AC 944 ms 896 KB
subtask_1_15.txt TLE 2103 ms 640 KB
subtask_1_16.txt TLE 2103 ms 1920 KB
subtask_1_17.txt WA 1347 ms 1664 KB
subtask_1_18.txt WA 8 ms 384 KB
subtask_1_19.txt TLE 2103 ms 3072 KB
subtask_1_20.txt TLE 2103 ms 3072 KB
subtask_1_21.txt TLE 2103 ms 1792 KB
subtask_1_22.txt TLE 2103 ms 1152 KB
subtask_1_23.txt TLE 2103 ms 2688 KB
subtask_1_24.txt TLE 2103 ms 3328 KB
subtask_1_25.txt TLE 2103 ms 3328 KB
subtask_1_26.txt TLE 2103 ms 3328 KB
subtask_1_27.txt TLE 2103 ms 3328 KB
subtask_1_28.txt TLE 2103 ms 3328 KB
subtask_1_29.txt TLE 2103 ms 3328 KB
subtask_1_30.txt TLE 2103 ms 3328 KB
subtask_1_31.txt TLE 2103 ms 3328 KB
subtask_1_32.txt TLE 2103 ms 3328 KB
subtask_1_33.txt TLE 2103 ms 3328 KB
subtask_1_34.txt TLE 2103 ms 3328 KB
subtask_1_35.txt TLE 2103 ms 3328 KB
subtask_1_36.txt WA 96 ms 3328 KB
subtask_1_37.txt TLE 2103 ms 3328 KB