Submission #89844

#	Time	Username	Problem	Language	Result	Execution time	Memory
89844		Bodo171	Divide and conquer (IZhO14_divide)	C++14	100 / 100	67 ms	9700 KiB

divide

#include <iostream>
#include <fstream>
#include <algorithm>
#include <climits>
using namespace std;
const int nmax=100005;
long long aib[nmax],x[nmax],d[nmax],g[nmax],norm[nmax];
long long sum,sumGold,ans;
int n,i,j;
inline int lbit(int x)
{
    return  ((x^(x-1))&x);
}
void update(int poz,long long val)
{
    for(int idx=poz;idx<=n;idx+=lbit(idx))
        aib[idx]=max(aib[idx],val);
}
long long compute(int poz)
{
    long long ret=LLONG_MIN;
    for(int idx=poz;idx>0;idx-=lbit(idx))
        ret=max(ret,aib[idx]);
    return ret;
}
int pos(long long val)
{
    int ret=0;
    for(int p=17;p>=0;p--)
        if(ret+(1<<p)<=n&&norm[ret+(1<<p)]<=val)
           ret+=(1<<p);
    return ret;
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>x[i]>>g[i]>>d[i];
        norm[i]=1LL*sum-x[i];
        sum+=d[i];
        aib[i]=LLONG_MIN;
    }
    sort(norm+1,norm+n+1);
    sum=0;sumGold=0;
    for(i=1;i<=n;i++)
    {
        update(pos(sum-x[i]),-sumGold);
        sum+=d[i];sumGold+=g[i];
        ans=max(ans,sumGold+compute(pos(sum-x[i])));
    }
    cout<<ans;
    return 0;
}

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