Submission #95548

#	Time	Username	Problem	Language	Result	Execution time	Memory
95548		easrui	도넛 (JOI14_ho_t3)	C++14	100 / 100	505 ms	3320 KiB

2014_ho_t3

#include <bits/stdc++.h>
using namespace std;
const int MN = 1e5+5;
int N,A[MN],sa,sb,sc,pos;
long long S[2*MN],tmp,sz,res,ans;
int main()
{
    //freopen("input.txt","r",stdin);
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=2*N; i++) S[i] = S[i-1] + A[(i-1)%N+1];
    while(sa<N){
        while(sz <= min(S[sc+1]-S[sb],S[sa+N]-S[sc+1])){
            sz = min(S[sc+1]-S[sb],S[sa+N]-S[sc+1]);
            sc++;
        }
        res = min(S[sb]-S[sa],sz);
        while(1){
            pos = sc;
            tmp = min(S[sc]-S[sb+1],S[sa+N]-S[sc]);
            while(tmp <= min(S[pos+1]-S[sb+1],S[sa+N]-S[pos+1])){
                tmp = min(S[pos+1]-S[sb+1],S[sa+N]-S[pos+1]);
                pos++;
            }
            if(res<=min(S[sb+1]-S[sa],tmp)){
                res = min(S[sb+1]-S[sa],tmp);
                sz = tmp;
                sc = pos;
                sb++;
            } else break;
        }
        ans = max(ans,res);
        sa++;
    }
    cout << ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 50 / 50