Submission #866138

#	Time	Username	Problem	Language	Result	Execution time	Memory
866138		Ellinor	Hacker (BOI15_hac)	C++14	100 / 100	294 ms	22536 KiB

hac

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize ("unroll-loops")

#pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
#pragma GCC target("movbe")                                      // byte swap
#pragma GCC target("aes,pclmul,rdrnd")                           // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")

typedef long long ll;
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
#define rrep(i, a, b) for (int i = (a) - 1; i >= int(b); i--)
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define pb push_back
#define all(x) x.begin(), x.end()

inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

ll INF = 1000000000;
ll mod = 1e9 + 7;

#define int ll
#define float double

//

int N;
vector<int> ns;
vector<pii> splits;

int32_t main()
{
    fast();
    cin >> N;
    ns.assign(N, -1);
    rep(i,0,N) {
        cin >> ns[i];
    }

    int hn = N / 2;
    int sum1 = 0, sum2 = 0;
    rep(i,0,hn) {
        sum1 += ns[i];
    }
    rep(i,hn,N) {
        sum2 += ns[i];
    }

    rep(i,0,N) {
        splits.pb({sum1, sum2});
        //
        sum2 += ns[i];
        sum1 -= ns[i];
        sum1 += ns[(i + hn) % N];
        sum2 -= ns[(i + hn) % N];
        //
    }

    int bans = 0;
    multiset<int> s;
    rep(i,0,N % 2 ? hn + 1 : hn) {
        s.insert(splits[i].second);
    }

    // rep(i,0,N) {
    //     cerr << splits[i].first << " " << splits[i].second << "\n";
    // }

    rep(i,0,N % 2 ? 2*N : N)
    {
        // cerr << "*";
        auto x = s.begin();
        int ans = *x;
        bans = max(bans, ans);

        if (N % 2) {
            s.erase(s.lower_bound(splits[i % N].second));
            s.insert(splits[(i + hn + 1) % N].second);
        }
        else {
            s.erase(s.lower_bound(splits[i % N].second));
            s.insert(splits[(i + hn) % N].second);
        }
    }

    cout << bans << "\n";
}

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