Pagini recente » Cod sursa (job #1410773) | Cod sursa (job #939222) | Cod sursa (job #731499) | Cod sursa (job #1948574) | Cod sursa (job #1862699)
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
struct concert{
int st;
int dr;
};
concert v[100000];
int cmp(concert a, concert b){
if(a.dr<b.dr)
return 1;
return 0;
}
int best[131073];
int maxim(int a, int b){
if(a<b)
a=b;
return a;
}
int main()
{
FILE *fin, *fout;
int n,a,b,i,j,max;
fin=fopen("heavymetal.in","r");
fout=fopen("heavymetal.out","w");
fscanf(fin,"%d",&n);
max=0;
for(i=0;i<n;i++){
fscanf(fin,"%d%d",&v[i].st,&v[i].dr);
if(max<v[i].dr)
max=v[i].dr;
}
sort(v,v+n,cmp);
j=0;
for(i=1;i<=max;i++){
best[i]=best[i-1];
while(v[j].dr<=i){
best[i]=maxim(best[i],best[v[j].st]+(v[j].dr-v[j].st));
j++;
}
}
fprintf(fout,"%d",best[max]);
fclose(fin);
fclose(fout);
return 0;
}