Pagini recente » Cod sursa (job #1896003) | Cod sursa (job #2319059) | Cod sursa (job #507749) | Cod sursa (job #3267993) | Cod sursa (job #2412660)
#include <iostream>
#include <algorithm>
#include <stdio.h>
#define NMAX 100000
using namespace std;
struct elem {
long long st ;
long long dr ;
};
elem v [ NMAX + 1 ] ;
long long d [ NMAX + 1 ] ;
bool comp (elem a, elem b) {
if (a.dr < b.dr )
return true;
else if (a.st < b.st )
return true ;
return false ;
}
long long binarys (long long val, long long n ) {
long long st, dr, mid ;
st = 1 ;
dr = n-1 ;
while (st < dr-1 ) {
mid = (st + dr ) / 2 ;
if (v[mid].dr > val)
dr = mid - 1 ;
else
st = mid ;
}
if(v[dr].dr <= val)
return dr ;
else
return st ;
}
int main() {
FILE *fin, *fout ;
fin = fopen ("heavymetal.in", "r" ) ;
fout = fopen ("heavymetal.out", "w" ) ;
long long n, i, poz, maxim ;
fscanf (fin, "%lld", &n ) ;
for (i = 1 ; i <= n ; i++ )
fscanf (fin, "%lld%lld", &v[i].st, &v[i].dr ) ;
sort(v+1, v+n+1, comp) ;
for (i = 1 ; i <= n ; i++ ) {
poz = binarys(v[i].st, i) ;
d[i] = max (d[poz] + (v[i].dr - v[i].st), d[i-1]) ;
}
fprintf (fout, "%lld ", d[n] ) ;
return 0;
}