Submission #1193419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193419		SnowRaven52	Hacker (BOI15_hac)	C++20	100 / 100	369 ms	18096 KiB

hac

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

int main() {
	// freopen("main.in", "r", stdin);
	// freopen(".out", "w", stdout);
    int n; cin >> n;
    vector<int> a(2 * n + 1);
    a[0] = 0;
    multiset<int> m;
    int wsz = (n + 1) / 2;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) a[n + i + 1] = a[i + 1];
    for (int i = 1; i <= 2 * n; i++) a[i] += a[i - 1];
    vector<int> mins(n+1, INT_MAX);
    for (int i = 1; i < 2*n + 1; i++) {
        if (i + wsz - 1 <= 2*n) {
            int sum = a[i+wsz-1] - a[i-1];
            m.insert(sum);
        }
        if (i > wsz) {
            int old = a[i-1] - a[i-1-wsz];
            m.erase(m.find(old));
        }
        int pos = ((i-1)%n) + 1;
        if (!m.empty()) mins[pos] = min(mins[pos], *m.begin());
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans = max(ans, mins[i]);
    cout << ans << endl;
}

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