Cod sursa(job #1265749)
| Utilizator | 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;
}
