Cod sursa(job #1754973)

Utilizator giotoPopescu Ioan gioto Data 9 septembrie 2016 02:09:06
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <cstdio>
#include <algorithm>
using namespace std;

int n,p[100002],best[100002];
struct interval{
    int x,y;
}a[100002];
bool cmp(int x,int y){
    if(a[x].y>a[y].y)return 0;
    if(a[x].y==a[y].y&&a[x].x>a[y].x)return 0;
    return 1;

}
int main()
{
    freopen("heavymetal.in", "r", stdin);
    freopen("heavymetal.out", "w", stdout);
    scanf("%d", &n);
    for(int i=1;i<=n;++i)
        scanf("%d%d", &a[i].x,&a[i].y),p[i]=i;
    sort(p+1,p+n+1,cmp);
    int Max=a[p[n]].y,j=1;
    for(int i=1;i<=Max;++i){
        best[i]=best[i-1];
        while(a[p[j]].y==i){
            best[i]=max(best[i],best[a[p[j]].x]+(a[p[j]].y-a[p[j]].x));
            ++j;
        }
    }printf("%d", best[Max]);
    return 0;
}