Cod sursa(job #1265749)

Utilizator cojocarugabiReality cojocarugabi Data 17 noiembrie 2014 18:32:22
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.52 kb
# include <bits/stdc++.h>
using namespace std;
ifstream fi("heavymetal.in");
ofstream fo("heavymetal.out");
struct cc
{
    int x,y;
} s[100005];
int d[int(1e6+5)];
bool cmp(cc a,cc b)
{
    return (a.y < b.y);
}
int main(void)
{
    int n;
    fi>>n;
    for (int i=1;i<=n;++i) fi>>s[i].x>>s[i].y;
    sort(s+1,s+1+n,cmp);
    for (int l=1,i=1;l<=s[n].y;++l)
    {
        d[l]=d[l-1];
        while (s[i].y == l) d[l]=max(d[l],d[s[i].x] + l - s[i].x),++i;
    }
    return fo << d[s[n].y] << '\n',0;
}