Submission #1171433

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171433		LmaoLmao	Hacker (BOI15_hac)	C++20	100 / 100	288 ms	18052 KiB

hac

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl '\n'
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using aa = array<ll,5>;

const int N = 1e6;
const int INF = 1e9;

int S[2000005],lz[2000005];
int pre[500005];

void push(int id) {
    S[id*2]=min(S[id*2],lz[id]);
    S[id*2+1]=min(S[id*2+1],lz[id]);
    lz[id*2]=min(lz[id*2],lz[id]);
    lz[id*2+1]=min(lz[id*2+1],lz[id]);
    lz[id]=1e9;
}
void update(int id,int l,int r,int u,int v,int val) {
    if(v < l || r < u) return;
    if(u<=l && r<=v) {
        //cout << l << ' ' << r << ' ' << id << endl;
        S[id]=min(S[id],val);
        lz[id]=min(lz[id],val);
        return;
    }
    push(id);
    int m=(l+r)/2;
    update(id*2,l,m,u,v,val);
    update(id*2+1,m+1,r,u,v,val);
    S[id]=min(S[id*2],S[id*2+1]);
}
int get(int id,int l,int r,int pos) {
    if(pos < l || r < pos) return 0;
    if(l==r) {
        return S[id];
    }
    push(id);
    int m=(l+r)/2;
    int t=get(id*2,l,m,pos);
    int t1=get(id*2+1,m+1,r,pos);
    return max(t,t1);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("CHONSO.inp", "r", stdin);
    //freopen("CHONSO.out", "w", stdout);
    int n;
    cin >> n;
    for(int i=1;i<=n*4;i++) {
        S[i]=1e9;
        lz[i]=1e9;
    }
    for(int i=1;i<=n;i++) {
        cin >> pre[i];
        pre[i]+=pre[i-1];
    }
    int k=(n+1)/2;
    for(int i=1;i<=n;i++) {
        ll sum,sum1;
        if(i<k) {
            sum=pre[i];
            sum+=pre[n]-pre[n-k+i];
            update(1,1,n,1,i,sum);
            update(1,1,n,n-k+i+1,n,sum);
            //cout << n << ' '<< endl;
        }
        else {
            sum=pre[i]-pre[i-k];
            update(1,1,n,i-k+1,i,sum);
        }
        //cout << get(1,1,n,2) << ' ';
    }
    int ans=0;
    for(int i=1;i<=n;i++) {
        //cout << get(1,1,n,i) << endl;
        ans=max(ans,get(1,1,n,i));
    }
    cout << ans;
    return 0;
}

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