oj.uz

Submission #89843

# Submission time Handle Problem Language Result Execution time Memory
89843 2018-12-18T14:43:02 Z Bodo171 Divide and conquer (IZhO14_divide) C++14
0 / 100
 1000 ms 144484 KB 
#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])));
        for(j=1;j<=n;j++)
            cout<<aib[j]<<' ';
        cout<<'\n';
    }
    cout<<ans;
    return 0;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1103 ms 144484 KB Time limit exceeded
2 Halted 0 ms 0 KB -