Pagini recente » Cod sursa (job #1573331) | Cod sursa (job #202978) | Cod sursa (job #793460) | Istoria paginii runda/boji_round2/clasament | Cod sursa (job #1851879)
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct eu{int x, y, val;};
eu v[100001];
int i, j, n, m, x, k;
bool sorting(eu a, eu b){
return a.y<b.y;
}
int main()
{
FILE *fin=fopen("heavymetal.in", "r");
FILE *fout=fopen("heavymetal.out", "w");
fscanf(fin,"%d", &n);
for(i=1; i<=n; i++)
fscanf(fin,"%d%d", &v[i].x, &v[i].y);
sort(v+1, v+n+1, sorting);
for(i=1; i<=n; i++){
int l1=1, l2=i-1, o=0;
while(l1<=l2){
int mid=(l1+l2)/2;
if(v[mid].y<=v[i].x){
o=mid;
l1=mid+1;
}
else
l2=mid-1;
}
v[i].val=max(v[i-1].val, v[i].y-v[i].x+v[o].val);
}
fprintf(fout,"%d\n", v[n].val);
return 0;
}