Pagini recente » Cod sursa (job #1671297) | Cod sursa (job #2984289) | Cod sursa (job #1061481) | Cod sursa (job #2636216) | Cod sursa (job #2208395)
#include <fstream>
using namespace std;
const int a=100005;
int dp[a],cnt,n,i;
struct tt
{
int st,dr;
}v[a],aux[a];
void merg(int l,int r)
{
if(l==r)
return;
int mij=(l+r)/2;
merg(l,mij);
merg(mij+1,r);
int i=l;
int j=mij+1;
cnt=0;
while(i<=mij&&j<=r)
{
if(v[i].dr<=v[j].dr)
aux[++cnt]=v[i++];
else aux[++cnt]=v[j++];
}
while(i<=mij)
aux[++cnt]=v[i++];
while(j<=r)
aux[++cnt]=v[j++];
for(i=l;i<=r;i++)
v[i]=aux[i-l+1];
}
int main()
{
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
cin>>n;
for(i=1;i<=n;i++)
cin>>v[i].st>>v[i].dr;
merg(1,n);
//for(i=1;i<=n;i++)
// cout<<v[i].st<<" "<<v[i].dr<<endl;
for(i=1;i<=n;i++)
{
int pos=0;
for(int j=1;j<i;j++)
if(v[i].st>=v[j].dr)
pos=j;
dp[i]=max(dp[i],dp[pos]+v[i].dr-v[i].st);
}
cout<<dp[n];
return 0;
}