Submission #1270648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270648		bjp123	Hacker (BOI15_hac)	C++20	100 / 100	226 ms	20008 KiB

hac

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define ii pair<ll, ll>
#define all(a) a.begin(), a.end()
#define iii pair<ll,ii>
using namespace std;


const ll N =1e6+5;
const ll mod = 998244353;
const ll inf=1e18;

ll n,i,j,m,q,k,t,x,y;
ll a[N];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n;
    a[0]=0;

    for(i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]+=a[i-1];
    }
    for(i=n+1;i<=n+n;i++)
        a[i]=a[i-n]-a[i-n-1]+a[i-1];
    multiset<ll> ms;
    for(i=n/2+1;i<=n;i++)
        ms.insert(a[i]-a[i-n/2]);

    ll res=a[n]-*(--ms.end());
    for(i=2;i<=n;i++)
        {
        ms.erase(ms.find(a[i+n/2-1]-a[i-1]));
        ms.insert(a[i+n-1]-a[i+n-1-n/2]);
        //cout<<i<<" "<<a[i+n/2]-a[i]<<" "<<a[i+n-1]-a[i+n-1-n/2]<<'\n';
        res=max(res,a[n]-*(--ms.end()));
        }
    cout<<res;
    return 0;
}
/*
4
7 6 8 4
2->4 14
3->5
4->6
5->7
2 3
3 4
2->n
3->n+1
*/

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