Pagini recente » Cod sursa (job #594538) | Cod sursa (job #3170184) | Cod sursa (job #457652) | Cod sursa (job #2300922) | Cod sursa (job #358397)
Cod sursa(job #358397)
#include<fstream>
#include<cstdlib>
using namespace std;
ifstream f1 ("heavymetal.in");
ofstream f2 ("heavymetal.out");
int n,best[1000001];
struct trupa {int a,b;};
trupa t[100001];
int max(int a, int b)
{
if (a>b) return a;
return b;
}
int cmp(const void *p,const void *q)
{
trupa x=*(trupa*)p,y=*(trupa*)q;
if(x.b<y.b)
return -1;
if(x.b>y.b)
return 1;
return 0;
}
int main()
{
int i,j,tmax=0;
f1>>n;
for (i=1; i<=n; i++) {f1>>t[i].a>>t[i].b; if (t[i].b>tmax) tmax=t[i].b;}
qsort (t+1,n,sizeof(t[0]),cmp);
int k=1;
for (i=1; i<=tmax; i++)
{
best[i]=best[i-1];
if (t[k].b==i)
{
best[i]=max(best[i], best[t[k].a] + (t[k].b - t[k].a));
k++;
}
}
f2<<best[tmax];
return 0;
}