제출 #476261

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
476261		ogibogi2004	금 캐기 (IZhO14_divide)	C++14	100 / 100	138 ms	8688 KiB

divide

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=1e5+6;
const ll INF=2e17;
int n;
ll x[MAXN],g[MAXN],d[MAXN],pref[MAXN];
ll fen[MAXN];
vector<ll>v;
void update(int idx,ll val)
{
    idx++;
    for(;idx<MAXN;idx+=idx&(-idx))
    {
        fen[idx]=max(fen[idx],val);
    }
}
ll query(int idx)
{
    idx++;
    ll ret=-INF;
    for(;idx>0;idx-=idx&(-idx))
    {
        ret=max(ret,fen[idx]);
    }
    return ret;
}
ll pref1[MAXN],output=0;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>g[i]>>d[i];
    }
    for(int i=1;i<MAXN;i++)
    {
        fen[i]=-INF;
    }
    v.push_back(0);
    for(int i=1;i<=n;i++)
    {
        pref[i]=pref[i-1]+d[i];
        pref1[i]=pref1[i-1]+g[i];
        v.push_back(pref[i]-x[i]);
        //cout<<i<<" "<<pref[i]-x[i]<<endl;
    }
    sort(v.begin(),v.end());
    for(int i=1;i<=n;i++)
    {
        //cout<<i<<":\n";
        ll t=pref[i-1]-x[i];
        int l=0,r=v.size()-1,ans=-1,mid;
        while(l<=r)
        {
            mid=(l+r)/2;
            if(t<=v[mid])
            {
                r=mid-1;
            }
            else
            {
                ans=mid;
                l=mid+1;
            }
        }
        ans++;
        //cout<<ans<<endl;
        update(ans+1,-pref1[i-1]);
        l=0,r=v.size()-1,ans=-1;
        t=pref[i]-x[i];
        while(l<=r)
        {
            mid=(l+r)/2;
            if(t<=v[mid])
            {
                r=mid-1;
            }
            else
            {
                ans=mid;
                l=mid+1;
            }
        }
        ans++;
        //cout<<ans<<endl;
        output=max(output,pref1[i]+query(ans+1));
    }
    cout<<output<<endl;
return 0;
}

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