oj.uz

답안 #5447

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
5447 2014-05-02T13:41:49 Z baneling100 금 캐기 (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

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

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

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