Pagini recente » Profil ionanghelina | Cod sursa (job #2088754) | Cod sursa (job #762406) | Cod sursa (job #3124010) | Cod sursa (job #178155)
Cod sursa(job #178155)
#include<fstream>
using namespace std;
struct Interval {
int inc, sf;
} a[100001], aux;
int n, s, best[100001],pos[100001], l;
int part(int st,int dr){
int i=st, j=dr, ii=0,jj=-1,au;
while(i<j){
if(a[i].sf>a[j].sf){
aux=a[i];
a[i]=a[j];
a[j]=aux;
au=ii;
ii=-jj;
jj=-au;
}
i+=ii;
j+=jj;
}
return i;
}
void qsort(int st, int dr){
if(st<dr){
int m=part(st,dr);
qsort(st,m-1);
qsort(m+1,dr);
}
}
inline int max(int a, int b){
return a>b?a:b;
}
int main(){
int i,j;
ifstream f("heavymetal.in");
f>>n;
for(i=1;i<=n;i++)
f>>a[i].inc>>a[i].sf;
f.close();
qsort(1,n);
for(i=1;i<=n;i++){
j=i;
while(a[j].sf==a[i].sf){
int k=j;
while(a[k].sf>a[j].inc) pos[j]=a[k--].sf;
pos[j]=a[k--].sf;
best[a[j].sf]=max(best[a[j].sf], best[pos[j]]+a[j].sf-a[j].inc);
j++;
}
}
ofstream g("heavymetal.out");
g<<best[a[n].sf]<<'\n';
g.close();
return 0;
}