Submission #335566

#	Time	Username	Problem	Language	Result	Execution time	Memory
335566		smax	Hacker (BOI15_hac)	C++17	100 / 100	437 ms	18540 KiB

hac

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

#ifdef LOCAL
#define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define DEBUG(...) 6;
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
template<typename T> void debug(string s, T x) {cerr << s << " = " << x << "\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...);}

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

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i=0; i<n; i++)
        cin >> a[i];

    vector<int> pref(n);
    for (int i=0; i<n; i++)
        pref[i] = a[i] + (i > 0 ? pref[i-1] : 0);

    auto query = [&] (int l, int r) {
        if (l <= r)
            return pref[r] - (l > 0 ? pref[l-1] : 0);
        else
            return pref[n-1] - (l > 0 ? pref[l-1] : 0) + pref[r];
    };

    multiset<int> st;
    for (int i=0; i<=(n-1)/2; i++)
        st.insert(query(i, (i + (n - 1) / 2) % n));

    int ret = *st.begin();
    for (int i=1; i<n; i++) {
        st.erase(st.find(query(i - 1, (i - 1 + (n - 1) / 2 + n) % n)));
        st.insert(query((i + (n - 1) / 2) % n, ((i + (n - 1) / 2) % n + (n - 1) / 2) % n));
        ret = max(ret, *st.begin());
    }
    cout << ret << "\n";

    return 0;
}

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