Submission #5447

#	Time	Username	Problem	Language	Result	Execution time	Memory
5447		baneling100	Divide and conquer (IZhO14_divide)	C++98	100 / 100	72 ms	6164 KiB

divide

#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;
}

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52