Cod sursa(job #2412631)

Utilizator alex.cojocaruAlex Cojocaru alex.cojocaru Data 22 aprilie 2019 14:02:44
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#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;
}