Cod sursa(job #158147)

Utilizator astronomyAirinei Adrian astronomy Data 13 martie 2008 14:33:42
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <vector>
#include <algorithm>
#include <stdio.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define PII pair<int,int>
#define x first
#define y second
#define MAXN 100100

int N, T[MAXN];
vector< PII > A;

int solve(void)
{
    int i, j, k; vector< PII >::iterator it;
    sort(A.begin(), A.end());
    for(i = N-1; i >= 0; i--)
    {
        T[i] = T[i+1], it = lower_bound(A.begin(), A.end(), mp(A[i].y,0));
        T[i] = max(T[i], A[i].y-A[i].x+T[(int)(it-A.begin())]);
    }
    return T[0];
}

int main(void)
{
    freopen("heavymetal.in", "rt", stdin);
    freopen("heavymetal.out", "wt", stdout);

    int i, a, b;
    scanf("%d\n", &N);
    for(i = 1; i <= N; i++) scanf("%d %d\n", &a, &b), A.pb(mp(a,b));

    printf("%d\n", solve());

    return 0;
}