oj.uz

Submission #5446

# Submission time Handle Problem Language Result Execution time Memory
5446 2014-05-02T13:40:29 Z baneling100 Divide and conquer (IZhO14_divide) C++
17 / 100
 4 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(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
0.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 Runtime error 4 ms 6160 KB SIGSEGV Segmentation fault
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6164 KB Output is correct
2 Correct 4 ms 6164 KB Output is correct
3 Runtime error 0 ms 6160 KB SIGSEGV Segmentation fault
4 Halted 0 ms 0 KB -