Pagini recente » Election | Monitorul de evaluare | Diferente pentru utilizator/eugenstoica intre reviziile 11 si 12 | Statistici Grigore Ioana (Ioana_Grigore) | Cod sursa (job #164016)
Cod sursa(job #164016)
#include <stdio.h>
#include <algorithm>
#define MAXN 100005
using namespace std;
struct concert
{
int s,e;
};
bool cmp(concert a, concert b)
{
return a.e<b.e;
}
concert v[MAXN],a[MAXN];
int n,m;
int cb(int x)
{
int s,e;
s=1;
e=m;
while(s<e)
{
if (x<=v[(s+e)/2].e)
e=(s+e)/2;
else
s=(s+e)/2+1;
}
if(x<v[s].e)
--s;
return s;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int i,p,profit;
scanf("%d",&n);
for (i=0; i<n; i++)
scanf("%d%d",&a[i].s,&a[i].e);
sort(a,a+n,cmp);
v[1].e=a[0].e;
v[1].s=a[0].e-a[0].s;
m=1;
for (i=1; i<n; i++)
{
p=cb(a[i].s);
profit=v[p].s+a[i].e-a[i].s;
if(a[i].e == v[m].e)
if(profit>v[m].s)
v[m].s=profit;
else;
else
{
if(profit<v[m].s)
profit=v[m].s;
v[++m].s=profit;
v[m].e=a[i].e;
}
}
printf("%d\n",v[m].s);
fclose(stdin);
fclose(stdout);
return 0;
}