Submission #1172272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172272		AlgorithmWarrior	금 캐기 (IZhO14_divide)	C++20	100 / 100	76 ms	3144 KiB

divide

#include <bits/stdc++.h>

using namespace std;

long long const INF=1e18;
int const MAX=1e5+5;
int const LOG=20;
int n;

int ub(int x){
    return x&(-x);
}

void maxself(long long& x,long long val){
    if(x<val)
        x=val;
}

struct AIB{
    long long maxim[MAX];
    int n;
    void init(int n){
        this->n=n;
        int i;
        for(i=1;i<=n;++i)
            maxim[i]=-INF;
    }
    void upd(long long val,int poz){
        while(poz<=n){
            maxself(maxim[poz],val);
            poz+=ub(poz);
        }
    }
    int bin_search(long long val){
        int poz=0;
        int i;
        for(i=LOG-1;i>=0;--i)
            if(poz+(1<<i)<=n && maxim[poz+(1<<i)]<val)
                poz+=(1<<i);
        return poz;
    }
}aib;

int x[MAX];
long long sumg[MAX],sumd[MAX];

void read(){
    cin>>n;
    int i;
    for(i=1;i<=n;++i){
        cin>>x[i]>>sumg[i]>>sumd[i];
        sumg[i]+=sumg[i-1];
        sumd[i]+=sumd[i-1];
    }
}

long long solve(){
    long long ans=0;
    int i;
    aib.init(n);
    for(i=1;i<=n;++i){
        aib.upd(x[i]-sumd[i-1],i);
        int poz=aib.bin_search(x[i]-sumd[i]);
        maxself(ans,sumg[i]-sumg[poz]);
    }
    return ans;
}

int main()
{
    read();
    cout<<solve();
    return 0;
}

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