oj.uz

Submission #17665

# Submission time Handle Problem Language Result Execution time Memory
17665 2016-01-08T17:00:18 Z ZiyaZa Divide and conquer (IZhO14_divide) C++14
100 / 100
 69 ms 7580 KB 
#include <iostream>
#include <cstdio>
#define pairr pair<long long,int>
#define f first
#define s second
using namespace std;
long long sumg[100010],sume[100010],a;
int n,x[100010],g[100010],e[100010],il,ir;
pairr sl[100010],sr[100010];
long long solve(int l, int r)
{
    if (l==r)
    {
        return g[l];
    }
    if (l==r-1)
    {
        if (e[l]+e[r]>=x[r]-x[l]) return g[l]+g[r];
        return max(g[l],g[r]);
    }
    int mid=(l+r)/2;
    long long ans=max(solve(l,mid),solve(mid+1,r));
    il=0;
    ir=0;
    for (int i=mid;i>=l;i--)
    {
        a=(i==0 ? sume[mid] : sume[mid]-sume[i-1])-(x[mid]-x[i]);
        while (il>0 && a>=sl[il-1].f)
        {
            il--;
        }
        sl[il].f=a;
        sl[il].s=i;
        il++;
    }
    for (int i=mid+1;i<=r;i++)
    {
        a=sume[i]-sume[mid]-(x[i]-x[mid+1]);
        while (ir>0 && a>=sr[ir-1].f)
        {
            ir--;
        }
        sr[ir].f=a;
        sr[ir].s=i;
        ir++;
    }

    for (int i=0;i<il;i++)
    {
        int flag=0;
        for (int j=ir-1;j>=0;j--)
        {
            if (sl[i].f+sr[j].f>=x[mid+1]-x[mid])
            {
                ans=max(ans,sl[i].s==0 ? sumg[sr[j].s] : sumg[sr[j].s]-sumg[sl[i].s-1]);
                flag=1;
                break;
            }
        }
        if (flag==0) break;
    }
    return ans;
}

int main()
{
    cin>>n;
    for (int i=0;i<n;i++)
    {
        scanf("%d%d%d",&x[i],&g[i],&e[i]);
        if (i==0)
        {
            sumg[i]=g[i];
            sume[i]=e[i];
        }
        else
        {
            sumg[i]=sumg[i-1]+g[i];
            sume[i]=sume[i-1]+e[i];
        }
    }
    cout<<solve(0,n-1)<<endl;
    return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7580 KB Output is correct
2 Correct 0 ms 7580 KB Output is correct
3 Correct 0 ms 7580 KB Output is correct
4 Correct 0 ms 7580 KB Output is correct
5 Correct 0 ms 7580 KB Output is correct
6 Correct 0 ms 7580 KB Output is correct
7 Correct 0 ms 7580 KB Output is correct
8 Correct 0 ms 7580 KB Output is correct
9 Correct 0 ms 7580 KB Output is correct
10 Correct 0 ms 7580 KB Output is correct
11 Correct 0 ms 7580 KB Output is correct
12 Correct 0 ms 7580 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7580 KB Output is correct
2 Correct 0 ms 7580 KB Output is correct
3 Correct 0 ms 7580 KB Output is correct
4 Correct 2 ms 7580 KB Output is correct
5 Correct 0 ms 7580 KB Output is correct
6 Correct 0 ms 7580 KB Output is correct
7 Correct 0 ms 7580 KB Output is correct
8 Correct 2 ms 7580 KB Output is correct
9 Correct 2 ms 7580 KB Output is correct
10 Correct 0 ms 7580 KB Output is correct
11 Correct 4 ms 7580 KB Output is correct
12 Correct 0 ms 7580 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7580 KB Output is correct
2 Correct 6 ms 7580 KB Output is correct
3 Correct 0 ms 7580 KB Output is correct
4 Correct 16 ms 7580 KB Output is correct
5 Correct 18 ms 7580 KB Output is correct
6 Correct 51 ms 7580 KB Output is correct
7 Correct 34 ms 7580 KB Output is correct
8 Correct 29 ms 7580 KB Output is correct
9 Correct 58 ms 7580 KB Output is correct
10 Correct 59 ms 7580 KB Output is correct
11 Correct 62 ms 7580 KB Output is correct
12 Correct 69 ms 7580 KB Output is correct