Pagini recente » Cod sursa (job #3302345) | Cod sursa (job #3347117) | Cod sursa (job #3305767) | Borderou de evaluare (job #3332245) | Cod sursa (job #3334900)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n,dp[100005];
struct interval
{
int st,dr;
};
interval v[100005];
int cmp(interval a, interval b)
{
if(a.dr!=b.dr) return a.dr<b.dr;
else return a.st<b.st;
}
int cb(int x, int dr)
{
int st=1;
int rez=0;
int mij=0;
while(st<=dr)
{
mij=(st+dr)/2;
if(v[mij].dr<=x)
{
rez=mij;
st=mij+1;
}
else
{
dr=mij-1;
}
}
return rez;
}
int main()
{
fin>>n;
for(int i=1;i<=n;i++)
{
fin>>v[i].st>>v[i].dr;
}
sort(v+1,v+n+1,cmp);
for(int i=1;i<=n;i++)
{
int ind=cb(v[i].st,i-1);
dp[i]=max(dp[i-1], dp[ind]+v[i].dr-v[i].st);
}
fout<<dp[n];
return 0;
}