제출 #1118651

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1118651		orcslop	Hacker (BOI15_hac)	C++17	100 / 100	228 ms	34192 KiB

hac

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
#define f first
#define s second
#define pii pair<int, int>

const int N = 5e5 + 5; 

int n; 
int v[N << 1]; 
multiset<int> ms; 
priority_queue<pii, vector<pii>, greater<pii>> pq; 

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n; 
    for(int i = 0; i < n; i++){
        cin >> v[i]; 
        v[i + n] = v[i]; 
    }
    for(int i = 1; i < 2 * n; i++){
        v[i] += v[i - 1]; 
    }
    auto get_sum = [&](int x) -> int{
        return v[x + (n - 1) / 2] - (x ? v[x - 1] : 0); 
    }; 
    for(int i = 0; i < n; i++){
        ms.insert(i); 
        pq.push({get_sum(i), i}); 
    }
    int ans = 0; 
    while(!pq.empty()){
        if(ms.size()) ans = pq.top().f; 
        else break; 
        auto x = pq.top().s, d = (n + 1) / 2; 
        pq.pop(); 
        while(d){
            auto it = ms.lower_bound(x); 
            while(it != ms.end() && *it <= x + d - 1) {
                ms.erase(it); 
                it = ms.lower_bound(x); 
            }
            d = max(0, x + d - n); 
            x = 0; 
        }
    }
    cout << ans << '\n'; 
    return 0; 
}

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