Submission #1346648

#TimeUsernameProblemLanguageResultExecution timeMemory
1346648SzymonKrzywdaHacker (BOI15_hac)C++20
100 / 100
212 ms15964 KiB
#include <iostream>
#include <vector>
#include <set>

using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;

#define ff first
#define ss second


bool in(int a, int b, int c) {
    if (a <= b) return a <= c && c <= b;
    else return !(a < c && c < b);
}

const int MAXN = 5e5 + 7;
int sum[MAXN];


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    
    vi tab(n);
    for (int & val : tab) cin >> val;

    int aktsum = 0;

    int len = n / 2;
    for (int i = 0; i < len; i++) {
        aktsum += tab[i];
    }


    int sum2 = 0;
    multiset<int> secik;
    for (int i = 0; i < n; i++) {
        sum[i] = aktsum;
        aktsum -= tab[i];
        aktsum += tab[(i + len) % n];
        if (!in(i, (i + len - 1) % n, 0)) secik.insert(sum[i]);
        sum2 += tab[i];
    }

    int ans = 0;

    for (int i = 0; i < n; i++) {
        ans = max(ans, sum2 - *secik.rbegin());
        secik.extract(sum[(i + 1) % n]);
        secik.insert(sum[(i - len + 1 + n) % n]);
    }

    cout << ans << '\n';
    

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...