제출 #1164420

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164420		ivaziva	Divide and conquer (IZhO14_divide)	C++20	100 / 100	82 ms	17320 KiB

divide

#include <bits/stdc++.h>

using namespace std;

#define MAXN 100001
#define MAXM 17
#define int long long

int n;
int x[MAXN],g[MAXN],d[MAXN];
int energy[MAXN],gold[MAXN];
int sparse[MAXM][MAXN],lg[MAXN];

void build()
{
    for (int i=2;i<MAXN;i++) lg[i]=lg[i/2]+1;
    for (int i=1;i<=n;i++) sparse[0][i]=x[i]-energy[i];
    for (int j=1;j<MAXM;j++)
    {
        for (int i=1;i+(1<<j)<=n+1;i++) sparse[j][i]=min(sparse[j-1][i],sparse[j-1][i+(1<<(j-1))]);
    }
}

int query(int l,int r) {int k=lg[r-l+1];return min(sparse[k][l],sparse[k][r-(1<<k)+1]);}

int32_t main()
{
    cin>>n;energy[0]=0;gold[0]=0;
    for (int i=1;i<=n;i++) {cin>>x[i]>>g[i]>>d[i];gold[i]=gold[i-1]+g[i];energy[i]=energy[i-1]+d[i];}
    build();int ans=0;
    for (int levo=1;levo<=n;levo++)
    {
        int l=levo,r=n,rez=-1;
        while (l<=r)
        {
            int mid=(l+r)/2;
            if (query(mid,n)<=x[levo]-energy[levo-1]) {rez=mid;l=mid+1;}
            else r=mid-1;
        }
        if (rez==-1) continue;
        ans=max(ans,gold[rez]-gold[levo-1]);
    }
    cout<<ans<<endl;
}

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52