Pagini recente » Cod sursa (job #54746) | Cod sursa (job #2489620) | Cod sursa (job #2913487) | Statistici Oops Oops (la_rollercoaster_trebuie_MOD_1000000007) | Cod sursa (job #2673074)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int nmax=100000;
long long dp[nmax+5],a[nmax],b[nmax],k,n;
void bubblesort()
{
int i,h,o;
o=1;
while(o==1)
{
o=0;
for(i=1;i<=n-1;i++)
{
if(b[i]>b[i+1])
{
h=b[i];
b[i]=b[i+1];
b[i+1]=h;
h=a[i];
a[i]=a[i+1];
a[i+1]=h;
o=1;
}
}
}
}
int main()
{
int i,s,d;
fin>>n;
for(i=1; i<=n; i++)
{
fin>>a[i]>>b[i];
}
bubblesort();
for(i=1;i<=n;i++)
{
s=i-1;
d=b[i]-a[i];
while(a[i]<b[s])
s--;
dp[i]=max(dp[i-1],dp[s]+d);
}
fout<<dp[n];
return 0;
}