Pagini recente » Cod sursa (job #1618505) | Cod sursa (job #693169) | Cod sursa (job #677014) | Cod sursa (job #477099) | Cod sursa (job #819026)
Cod sursa(job #819026)
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct el
{
int A,B;
}v[100001];
int cmp(el a,el b)
{
if(a.B!=b.B)
return a.B>b.B;
else
return a.A>b.A;
}
int maxi(int a,int b)
{
if(a>b)
return a;
return b;
}
int ma,i,m,D[100000000],n,j,OK;
int main ()
{
f>>n;
for(i=1;i<=n;++i)
{
f>>v[i].A>>v[i].B;
if(v[i].B>m)
m=v[i].B;
}
sort(v+1,v+n+1,cmp);
j=n;
for(i=0;i<=m;++i)
{
D[i]=D[i-1];
if(v[j].B<=i)
for(;j>=1&&v[j].B<=i;--j)
{
if(v[j].B==i)
{
D[i]=maxi(D[v[j].A]+(v[j].B-v[j].A),D[i]);
}
}
}
for(i=1;i<=m;++i)
{
if(D[i]>ma)
ma=D[i];
}
g<<ma;
return 0;
}