Pagini recente » Cod sursa (job #2782283) | Cod sursa (job #1116524) | Cod sursa (job #362334) | Cod sursa (job #1697049) | Cod sursa (job #1684073)
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct cell
{
int st, dr;
}v[100002];
int n,dp[100002];
bool cmp(cell a,cell b)
{
return a.dr<b.dr;
}
int main()
{
f>>n;
for(int i=1;i<=n;i++)
f>>v[i].st>>v[i].dr;
sort(v+1,v+n+1,cmp);
for(int i=1;i<=n;i++)
{
int st=1;
int dr=i-1;
while(st<=dr)
{
int mij=(st+dr)/2;
if(v[mij].dr<=v[i].st)
st=mij+1;
else
dr=mij-1;
}
dp[i]=max(dp[i-1],dp[dr]+(v[i].dr-v[i].st));
}
g<<dp[n];
return 0;
}