Submission #485797

#	Time	Username	Problem	Language	Result	Execution time	Memory
485797		radal	Hacker (BOI15_hac)	C++14	100 / 100	312 ms	18404 KiB

hac

#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
typedef pair<long double,long double> pld;
const long long int N = 5e5+10,mod = 1e9+7,inf = 1e9,sq = 500;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
inline int poww(int n,ll k){
    int c = 1;
    while (k){
        if (k&1) c = (1ll*c*n)%mod;
        n = (1ll*n*n)%mod;
        k >>= 1;
    }
    return c;
}
int a[N],pre[N];
int main(){
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,sum = 0;
    cin >> n;
    rep(i,0,n) cin >> a[i],sum+=a[i];
    int ans = inf+10;
    repr(i,n/2-1,0) pre[n/2-1] += a[i];
    rep(i,n/2,n)
        pre[i] = pre[i-1]+a[i]-a[i-n/2];
    repr(i,n/2-2,0)
        pre[i] = pre[i+1]-a[i+1]+a[n-(n/2-1-i)];
    set<pll> st;
    rep(i,1,(n+1)/2+1){
        st.insert({pre[i-1+n/2],i});
        ans = min(ans,sum-pre[i-1+n/2]);
    }
    int ind = (n+1)/2+1;
    rep(i,1,n){
        st.erase({pre[(i-1+n/2)%n],i});
        st.insert({pre[i-1],ind});
        ind ++;
        if (ind >= n) ind -= n;
        ans = max(ans,sum-st.rbegin()->X);
    }
    cout << ans;
}

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