Submission #1358961

#TimeUsernameProblemLanguageResultExecution timeMemory
1358961njoopHacker (BOI15_hac)C++20
20 / 100
197 ms21968 KiB
#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, sum=0, ans=1e9;
    cin >> n;
    vector<int> arr(n+2, 0), pf(2*n+2, 0), p(2*n+2, 0);
    for(int i=1; i<=n; i++) {
        cin >> arr[i];
        sum += arr[i];
    }
    for(int i=1; i<=2*n; i++) {
        if(i <= n) pf[i] = pf[i-1] + arr[i];
        else pf[i] = pf[i-1] + arr[i-n];
    }
    for(int i=1; i<=n+n/2; i++) {
        p[i] = pf[i+n/2-1] - pf[i-1];
    }
    multiset<int> s;
    for(int i=1; i<=n/2; i++) {
        s.insert(p[i]);
    }
    ans = min(ans, *s.rbegin());
    for(int i=2; i<=n; i++) {
        s.erase(s.find(p[i-1]));
        s.insert(p[i+n/2-1]);
        ans = min(ans, *s.rbegin());
    }
    cout << sum-ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...