Pagini recente » Cod sursa (job #2242986) | Cod sursa (job #2440781) | Cod sursa (job #2450653) | Cod sursa (job #349184) | Cod sursa (job #2208396)
#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;
int lef=1,rig=i-1;
while(lef<=rig)
{
int mij=(lef+rig)/2;
if(v[mij].dr<=v[i].st)
{
pos=mij;
lef=mij+1;
}
else rig=mij-1;
}
dp[i]=max(dp[i-1],dp[pos]+v[i].dr-v[i].st);
}
cout<<dp[n];
return 0;
}