Submission #723560

#	Time	Username	Problem	Language	Result	Execution time	Memory
723560		sunnat	Hacker (BOI15_hac)	C++14	100 / 100	346 ms	35540 KiB

hac

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
using namespace std;
#define int long long
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n;
    m = (n+1)/2;
    vector<int>a(3*n+1), s(3*n+1);
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        a[i+n] = a[i+2*n] = a[i];
    }
    multiset<int> ms;
    for(int i = 1; i < m; i ++)
        s[i] = s[i-1] + a[i];
    for(int i = m; i < 2*m; i ++){
        s[i] = s[i-1] - a[i-m] + a[i];
        ms.insert(s[i]);
    }
    int res = *ms.begin();
    for(int i = m; i < n + m; i ++){
        ms.erase(ms.find(s[i]));
        s[i+m] = s[i+m-1] - a[i] + a[i+m];
        ms.insert(s[i+m]);
        res = max(res, *ms.begin());
    }

    cout << res;
    return 0;
}

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