제출 #1342171

#제출 시각아이디문제언어결과실행 시간메모리
1342171tsetsenbilegHacker (BOI15_hac)C++20
100 / 100
328 ms26008 KiB
#include <bits/stdc++.h>
#define int long long
using ld = long double;
#define pr pair<int, int>
#define pb push_back
using namespace std;
const int INF = 1e18+1, MOD = 998244353, MAXN = 4e5+5, MAXA = 41;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& i : a) cin >> i;
    for (int i = 0; i < n; i++) a.pb(a[i]);
    int k = (n+1) / 2;
    int sum = 0;
    for (int i = 0; i < k-1; i++) {
        sum += a[i];
    }
    vector<int> sums;
    for (int i = k-1; i < n+k-1; i++) {
        sum += a[i];
        sums.pb(sum);
        sum -= a[i-k+1];
    }
    deque<int> order;
    multiset<int> cur;
    for (int i = n-k+1; i < n; i++) {
        order.pb(sums[i]);
        cur.insert(sums[i]);
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        cur.insert(sums[i]);
        order.pb(sums[i]);
        res = max(res, *cur.begin());
        cur.erase(cur.find(order.front()));
        order.pop_front();
    }
    cout << res;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // int T;
    // cin >> T;
    // while (T--)
    solve();
    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...