oj.uz

Submission #5447

# Submission time Handle Problem Language Result Execution time Memory
5447 2014-05-02T13:41:49 Z baneling100 Divide and conquer (IZhO14_divide) C++
100 / 100
 72 ms 6164 KB 
#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.0 / 17.0

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

Subtask #2
31.0 / 31.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6164 KB Output is correct
2 Correct 0 ms 6164 KB Output is correct
3 Correct 4 ms 6164 KB Output is correct
4 Correct 20 ms 6164 KB Output is correct
5 Correct 32 ms 6164 KB Output is correct
6 Correct 52 ms 6164 KB Output is correct
7 Correct 44 ms 6164 KB Output is correct
8 Correct 28 ms 6164 KB Output is correct
9 Correct 44 ms 6164 KB Output is correct
10 Correct 72 ms 6164 KB Output is correct
11 Correct 68 ms 6164 KB Output is correct
12 Correct 72 ms 6164 KB Output is correct