Submission #703863

#	Time	Username	Problem	Language	Result	Execution time	Memory
703863		_martynas	Hacker (BOI15_hac)	C++11	100 / 100	112 ms	34128 KiB

hac

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }

const int MXN = 5e5+5;

int n;
ll A[2*MXN], pref[2*MXN];

int par[2*MXN], sz[2*MXN];
void init_dsu() {
    iota(par, par+2*n, 0);
    fill(sz, sz+2*n, 1);
}

int find_set(int a) {
    return par[a] == a ? a : par[a] = find_set(par[a]);
}

void unite(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if(a == b) return;
    if(sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    par[b] = a;
}

int main() {
    FASTIO();
    cin >> n;
    for(int i = 0; i < n; i++) cin >> A[i], A[i+n] = A[i];
    pref[0] = A[0];
    for(int i = 1; i < 2*n; i++) pref[i] = pref[i-1]+A[i];
    vector<pli> B;
    for(int i = 0; i < n; i++) {
        B.PB({pref[i+(n+1)/2-1]-(i?pref[i-1]:0), (i+(n+1)/2)%n});
    }
    sort(rall(B));
    vector<bool> active(2*n);
    auto activate = [&](int i) {
        active[i] = true;
        if(i && active[i-1]) {
            unite(i, i-1);
        }
        if(i+1<2*n && active[i+1]) {
            unite(i, i+1);
        }
        return sz[find_set(i)];
    };
    init_dsu();
    for(auto p : B) {
        int res = 0;
        res = max(activate(p.S), activate(p.S+n));
        if(res >= (n+1)/2) {
            cout << p.F << "\n";
            return 0;
        }
    }
    return 0;
}

/*



*/

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