Pagini recente » Cod sursa (job #2922025) | Cod sursa (job #1009376) | Cod sursa (job #13261) | Cod sursa (job #954590) | Cod sursa (job #182157)
Cod sursa(job #182157)
#include<fstream.h>
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct interval
{int a,b;}v[100001];
int n,s[100001],tmax;
int poz(int i,int j)
{int i1[2]={1,0},j1[2]={0,-1},k=0;
interval aux;
while(i<j)
{if(v[i].b>v[j].b)
{aux=v[i];
v[i]=v[j];
v[j]=aux;
k++;
}
i+=i1[k%2];
j+=j1[k%2];
}
return i;
}
void sortare(int i,int j)
{if(i<j)
{int p=poz(i,j);
sortare(i,p-1);
sortare(p+1,j);
}
}
int cauta(int i,int j,int x)
{if(i>j) return 0;
int m=(i+j)/2;
if(v[m].b>x) return cauta(i,m-1,x);
int ok=cauta(m+1,j,x);
if(ok>m) return ok;
return m;
}
int main()
{fin>>n;
int i,p;
for(i=1;i<=n;i++) fin>>v[i].a>>v[i].b;
sortare(1,n);
s[1]=v[1].b-v[1].a;
for(i=2;i<=n;i++)
{s[i]=s[i-1];
p=cauta(1,i-1,v[i].a);
if(s[p]+v[i].b-v[i].a>s[i]) s[i]=s[p]+v[i].b-v[i].a;
}
fout<<s[n];
fin.close();
fout.close();
return 0;
}