Cod sursa(job #2412498)

Utilizator isa_tudor_andreiAndrei Tudor isa_tudor_andrei Data 22 aprilie 2019 12:21:07
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>
#include <algorithm>

using namespace std;

int n;

struct COSTIN {
  long long st,dr;
}v[100001];

long long d[100001];

bool cmp( COSTIN a, COSTIN b ) {
  if( a.dr == b.dr )
    return a.st < b.st;
  return a.dr < b.dr;
}

int bs( int x ) {
  int l,r,mid,last = 1;
  l = 1;
  r = x - 1;
  while( l <= r ) {
    mid = ( l + r ) / 2;
    if( v[mid].dr <= v[x].st ) {
      l = mid + 1;
      last = mid;
    }
    else
      r = mid - 1;
  }
  return last;
}

int main() {
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    int i,j;
    scanf("%d",&n);
    for( i = 1; i <= n; i ++ ) {
      scanf("%lld%lld",&v[i].st,&v[i].dr);
    }
    sort( v + 1, v + n + 1, cmp );
    long long m = 0;
    d[0] = v[0].dr - v[0].st;
    for( i = 1; i <= n; i ++ ) {
      j = bs(i);
      d[i] = max( d[i-1],d[j]+(v[i].dr-v[i].st));
      if( m < d[i] )
         m = d[i];
    }
    printf("%lld",m);
    return 0;
}