oj.uz

Submission #89844

# Submission time Handle Problem Language Result Execution time Memory
89844 2018-12-18T14:43:34 Z Bodo171 Divide and conquer (IZhO14_divide) C++14
100 / 100
 67 ms 9700 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])));
    }
    cout<<ans;
    return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 448 KB Output is correct
4 Correct 2 ms 524 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 2 ms 728 KB Output is correct
9 Correct 2 ms 728 KB Output is correct
10 Correct 2 ms 728 KB Output is correct
11 Correct 1 ms 728 KB Output is correct
12 Correct 2 ms 728 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 728 KB Output is correct
2 Correct 3 ms 728 KB Output is correct
3 Correct 2 ms 728 KB Output is correct
4 Correct 3 ms 728 KB Output is correct
5 Correct 3 ms 728 KB Output is correct
6 Correct 4 ms 728 KB Output is correct
7 Correct 3 ms 728 KB Output is correct
8 Correct 3 ms 728 KB Output is correct
9 Correct 3 ms 740 KB Output is correct
10 Correct 3 ms 896 KB Output is correct
11 Correct 6 ms 1076 KB Output is correct
12 Correct 4 ms 1232 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1232 KB Output is correct
2 Correct 8 ms 1432 KB Output is correct
3 Correct 7 ms 1432 KB Output is correct
4 Correct 31 ms 2968 KB Output is correct
5 Correct 33 ms 2968 KB Output is correct
6 Correct 67 ms 4888 KB Output is correct
7 Correct 59 ms 5020 KB Output is correct
8 Correct 60 ms 5020 KB Output is correct
9 Correct 61 ms 5020 KB Output is correct
10 Correct 58 ms 5020 KB Output is correct
11 Correct 61 ms 7348 KB Output is correct
12 Correct 62 ms 9700 KB Output is correct