Submission #729554

#	Time	Username	Problem	Language	Result	Execution time	Memory
729554		Tigerpants	Hacker (BOI15_hac)	C++17	100 / 100	423 ms	25368 KiB

hac

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>
#include <functional>

using namespace std;

typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef map<ll, ll> mll_ll;

#define rep(i, a, b) for (ll i = a; i < b; i++)

ll N;
vll v;
vll dv;

ll get_slice(ll f, ll s) {
    return dv[s + 1] - dv[f] + ((f > s) ? dv[N] : 0);
}

ll half_N;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    half_N = (N + 1) / 2;
    v.resize(N);
    dv.resize(N + 1);
    dv[0] = 0;
    rep(i, 0, N) {
        cin >> v[i];
        dv[i + 1] = dv[i] + v[i];
    }

    ll best = 0;
    mll_ll slices;
    rep(i, 0, half_N) {
        slices[get_slice(i, (i + half_N - 1) % N)]++;
    }

    rep(i, 0, N) {
        best = max<ll>(best, slices.begin()->first);
        slices[get_slice(i, (i + half_N - 1) % N)]--;
        if (slices[get_slice(i, (i + half_N - 1) % N)] == 0) slices.erase(get_slice(i, (i + half_N - 1) % N));
        slices[get_slice((i + half_N) % N, ((2 * half_N) + i - 1) % N)]++;
    }

    cout << best << endl;

    return 0;
}

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