Pagini recente » Cod sursa (job #219279) | Cod sursa (job #2980205) | Cod sursa (job #889471) | Cod sursa (job #1672680) | Cod sursa (job #3224296)
#include <bits/stdc++.h>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int n;
int timp[100005],ans;
struct concert
{
int p,u;
} v[100005];
int comp(concert a, concert b)
{
if(a.u==b.u) return a.p<b.p;
else return a.u<b.u;
}
int caut(int x)
{
int m,p=1,u=n;
while (p<=u)
{
int m=(p+u)/2;
if (v[m].u<=v[x].p) p=m+1;
else u=m-1;
}
return u;
}
void dp()
{
int i,j;
for(i=1; i<=n; i++)
{
j=caut(i);
timp[i]=max(timp[i-1],timp[j]+v[i].u-v[i].p);
ans=max(ans,timp[i]);
}
g<<ans;
}
int main()
{
f>>n;
for(int i=1; i<=n; i++)
f>>v[i].p>>v[i].u;
sort(v+1,v+n+1,comp);
dp();
return 0;
}