Submission #564367

#	Time	Username	Problem	Language	Result	Execution time	Memory
564367		KoD	Hacker (BOI15_hac)	C++17	100 / 100	52 ms	11744 KiB

hac

#include <bits/stdc++.h>

using std::deque;
using std::pair;
using std::vector;

class SlidingMinimum {
    int push_i, pop_i;
    deque<pair<int, int>> deq;

  public:
    SlidingMinimum() : push_i(0), pop_i(0), deq() {}

    void push(const int x) {
        while (!deq.empty() and deq.back().first >= x) {
            deq.pop_back();
        }
        deq.emplace_back(x, push_i++);
    }

    void pop() {
        if (deq.front().second == pop_i) {
            deq.pop_front();
        }
        pop_i += 1;
    }

    int min() const { return deq.front().first; }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    vector<int> V(N);
    for (auto& x : V) {
        std::cin >> x;
    }
    vector<int> sum(2 * N + 1);
    for (int i = 0; i < N; ++i) {
        sum[i + 1] = sum[i] + V[i];
    }
    for (int i = 0; i < N; ++i) {
        sum[i + N + 1] = sum[i + N] + V[i];
    }
    const int len = (N + 1) / 2;
    vector<int> take(N);
    for (int i = 0; i < N; ++i) {
        take[i] = sum[i + len] - sum[i];
    }
    SlidingMinimum window;
    for (int i = N - len; i < N; ++i) {
        window.push(take[i]);
    }
    int ans = 0;
    for (int i = 0; i < N; ++i) {
        window.pop();
        window.push(take[i]);
        ans = std::max(ans, window.min());
    }
    std::cout << ans << '\n';
    return 0;
}

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