제출 #5447

#제출 시각아이디문제언어결과실행 시간메모리
5447baneling100Divide and conquer (IZhO14_divide)C++98
100 / 100
72 ms6164 KiB
#include <stdio.h>
#include <algorithm>

using namespace std;

pair <long long,int> a[100001];
pair <long long,int> b[100001];
int N, x[100001];
long long g[100001], d[100001], ans;

void input(void)
{
    int i;

    scanf("%d",&N);
    for(i=1 ; i<=N ; i++)
    {
        scanf("%d %lld %lld",&x[i],&g[i],&d[i]);
        g[i]+=g[i-1];
        d[i]+=d[i-1];
        a[i]=make_pair(d[i]-x[i],i);
        b[i]=make_pair(d[i-1]-x[i],i);
    }
    sort(a+1,a+N+1);
    sort(b+1,b+N+1);
}

void process(void)
{
    int i, top=0, mmin=N+1;

    for(i=1 ; i<=N ; i++)
    {
        while(top+1<=N && a[i].first>=b[top+1].first)
        {
            top++;
            if(mmin>b[top].second)
                mmin=b[top].second;
        }
        if(a[i].second>=mmin)
            if(ans<g[a[i].second]-g[mmin-1])
                ans=g[a[i].second]-g[mmin-1];
    }
}

void output(void)
{
    printf("%lld",ans);
}

int main(void)
{
    input();
    process();
    output();

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...