Submission #723720

#	Time	Username	Problem	Language	Result	Execution time	Memory
723720		kas_s	Hacker (BOI15_hac)	C++17	60 / 100	202 ms	3492 KiB

hac

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N;
    cin >> N;
    vector<int> a(N);
    long long s = 0;
    for (int &v: a) {
        cin >> v;
        s += v;
    }
    if (N <= 5000) {
        long long res = 0;
        for (int i = 0; i < N; i++) {
            long long window = 0;
            int len = N / 2;
            for (int j = i+1; j < i + len + 1; j++) window += a[j % N];
            long long curr = s - window;
            for (int r = i + len + 1; r % N != i; r++) {
                window += a[r % N];
                window -= a[(r - len) % N];
                curr = min(curr, s - window);
            }
            res = max(res, curr);
        }
        cout << res;
        return 0;
    }
    long long window = 0;
    int len = N / 2;
    for (int j = 1; j < len + 1; j++) window += a[j % N];
    long long curr = s - window;
    for (int r = len + 1; r % N != 0; r++) {
        window += a[r % N];
        window -= a[(r - len) % N];
        curr = min(curr, s - window);
    }
    cout << curr;
    return 0;
}

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