Submission #335567

#	Time	Username	Problem	Language	Result	Execution time	Memory
335567		smax	Hacker (BOI15_hac)	C++17	100 / 100	63 ms	6380 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...);}

template<typename T>
struct MinDeque {
    int l = 0, r = 0;
    deque<pair<T, int>> dq;

    void push(T x) {
        while (!dq.empty() && x <= dq.back().first)
            dq.pop_back();
        dq.emplace_back(x, r++);
    }

    void pop() {
        assert(l < r);
        if (dq.front().second == l++)
            dq.pop_front();
    }

    T min() {
        assert(!dq.empty());
        return dq.front().first;
    }
};

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];
    };

    MinDeque<int> dq;
    for (int i=0; i<=(n-1)/2; i++)
        dq.push(query(i, (i + (n - 1) / 2) % n));

    int ret = dq.min();
    for (int i=1; i<n; i++) {
        dq.push(query((i + (n - 1) / 2) % n, ((i + (n - 1) / 2) % n + (n - 1) / 2) % n));
        dq.pop();
        ret = max(ret, dq.min());
    }
    cout << ret << "\n";

    return 0;
}

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