oj.uz

답안 #17665

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
17665 2016-01-08T17:00:18 Z ZiyaZa 금 캐기 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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