Cod sursa(job #916350)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 16 martie 2013 13:19:29
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include<stdio.h>
#include<algorithm>
#define x first
#define y second
using namespace std;
pair<int , int> a[100007];
int b[100007];
bool cmp(pair<int , int> a , pair<int , int> b)
{
    return a.y < b.y;
}
int main()
{
    freopen("heavymetal.in" , "r" , stdin);
    freopen("heavymetal.out" , "w" , stdout);
    int last = 1 , n = 0;
    scanf("%ld",&n);
    for (int i=1 ; i<=n ; ++i)
        scanf("%ld%ld" , &a[i].x , &a[i].y);
    sort(a+1 , a+n+1 , cmp);
    for (int i=1 ; i<=a[n].y ; ++i)
    {
        b[i] = b[i-1];
        while (a[last].y == i)
        {
            if (b[i] < b[a[last].x] - a[last].x + i)
                b[i] = b[a[last].x] - a[last].x + i;
            ++last;
        }
    }
    printf("%ld" , b[a[n].y]);
    return 0;
}