Submission #1118656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118656		orcslop	Hacker (BOI15_hac)	C++17	100 / 100	225 ms	34280 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()) break; 
        ans = pq.top().f; 
        int x = pq.top().s; 
        int d = (n + 1) / 2; 
        pq.pop(); 
        while(d){
            auto it = ms.lower_bound(x); 
            while(it != ms.end() && *it < x + d) {
                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