Pagini recente » Cod sursa (job #1616788) | Cod sursa (job #835312) | Cod sursa (job #49212) | Cod sursa (job #2890193) | Cod sursa (job #2628811)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int n,i,dp[100005],m,ans;
struct trupe
{
int s,f;
}v[100005];
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
bool comp(trupe a, trupe b)
{
return a.f<b.f;
}
int cautbin(int val, int st, int dr)
{
ans=0;
while (st<=dr)
{
m=(st+dr)/2;
if (v[m].f<=val)
{
ans=m;
st=m+1;
}
else dr=m-1;
}
return ans;
}
int main()
{
in>>n;
for (i=1;i<=n;i++)
in>>v[i].s>>v[i].f;
sort(v+1,v+n+1,comp);
dp[1]=v[1].f-v[1].s;
for (i=2;i<=n;i++)
{
int p=cautbin(v[i].s,1,i-1);
dp[i]=max(dp[i-1],dp[p]+v[i].f-v[i].s);
}
out<<dp[n];
}