제출 #1315802

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1315802		999captain	Hacker (BOI15_hac)	C++20	100 / 100	99 ms	12496 KiB

hac

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
int n;
int v[500010],p[500010];
stack<pii> s1,s2;

void add(int t){
    if(s1.empty()){
        s1.push({t , t});
        return;
    }
    s1.push({t , min(t , s1.top().second)});
}

void remove(){
    if(s2.empty()){
        while(!s1.empty()){
            int t = s1.top().first;
            s1.pop();
            if(s2.empty()){
                s2.push({t , t});
            }
            else{
                s2.push({t , min(t , s2.top().second)});
            }
        }
    }
    s2.pop();
}

int query(){
    if(s2.empty()){
        return s1.top().second;
    }
    else if(s1.empty()){
        return s2.top().second;
    }
    else{
        return min(s1.top().second, s2.top().second);
    }

}

signed main(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> v[i];
    }
    int d = (n + 1)/2;
    for(int i = 1;i <= d;i++){
        p[1] += v[i];
    }
    for(int i = 2;i <= n;i++){
        p[i] = p[i - 1] - v[i - 1];
        if(i + d - 1 <= n){
            p[i] += v[i + d - 1];
        }
        else{
            p[i] += v[i + d - 1 - n];
        }
    }
    int ans = 0;
    for(int i = 1;i <= d;i++){
        add(p[i]);
    }
    for(int i = 1;i <= n;i++){
        ans = max(ans, query());
        remove();
        if(d + i <= n){
            add(p[d + i]);
        }
        else{
            add(p[d + i - n]);
        }
    }
    cout << ans << "\n";

}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 40 / 40