Pagini recente » Cod sursa (job #1918261) | Cod sursa (job #1072371) | Cod sursa (job #207888) | Cod sursa (job #2019407) | Cod sursa (job #2412631)
#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;
return false ;
}
long long binarys (long long val, long long n ) {
long long st, dr, mid ;
st = 0 ;
dr = n ;
while (st < dr ) {
mid = (st + dr ) / 2 ;
if (v[mid].dr >= val)
dr = mid ;
else
st = mid + 1 ;
}
return dr ;
}
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 = 0 ; i < n ; i++ )
fscanf (fin, "%lld%lld", &v[i].st, &v[i].dr ) ;
sort(v, v+n, comp) ;
d[0] = v[0].dr - v[0].st ;
for (i = 1 ; i < n ; i++ ) {
poz = binarys(v[i].st, i) ;
d[i] = d[poz] + (v[i].dr - v[i].st) ;
}
maxim = 0 ;
for (i = 0 ; i < n ; i++ ) {
if (d[i] > maxim )
maxim = d[i] ;
}
fprintf (fout, "%lld ", maxim ) ;
return 0;
}