Pagini recente » Cod sursa (job #2082036) | Cod sursa (job #2848390) | Cod sursa (job #2148911) | Cod sursa (job #1236284) | Cod sursa (job #388377)
Cod sursa(job #388377)
#include<fstream>
#define dmax 100003
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
int n;
long long dn[dmax],pr[dmax];
struct sp
{ long long p1;
long long p2;
} s[dmax] ;
typedef int (*compfn)(const void*,const void*);
int sf(struct sp *a,struct sp *b)
{ return a->p2 - b->p2;
}
int main()
{ int i,j,ok;
in>>n;
for(i=0;i<n;i++)
in>>s[i].p1>>s[i].p2;
in.close();
qsort((void*)&s, n, sizeof(struct sp), (compfn)sf);
for(i=n-1;i>0;i--)
{ ok=1;
for(j=i-1;j>=0 && ok;j--)
if(s[j].p2<=s[i].p1)
{ ok=0;
pr[i]=j;
}
}
for(i=0;i<n;i++)
{ if(i==0)
dn[i]=s[i].p2-s[i].p1;
else
dn[i]=s[i].p2-s[i].p1+dn[pr[i]];
}
out<<dn[n-1];
out.close();
return 0;
}