Submission #542412

#	Time	Username	Problem	Language	Result	Execution time	Memory
542412		pokmui9909	도넛 (JOI14_ho_t3)	C++17	100 / 100	28 ms	4436 KiB

2014_ho_t3

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N;
ll A[200005];
ll S[200005];

int main(){
    cin.tie(0) -> sync_with_stdio(false);

    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> A[i];
        A[i + N] = A[i];
    }
    for(int i = 1; i <= 2 * N; i++){
        S[i] = S[i - 1] + A[i];
    }
    ll L = 1, R = 1, ans = 0;
    while(L <= R && L <= N && R <= 2 * N && R - L + 1 <= N){
        ll V = S[R] - S[L - 1];
        ll idx = upper_bound(S + R + 1, S + L + N, S[R] + V) - S;
        if(S[L + N - 1] - S[idx] >= V){
            ans = max(ans, V);
            R++;
        } else {
            L++;
        }
    }
    cout << ans;
}

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