Cod sursa(job #2412517)

Utilizator isa_tudor_andreiAndrei Tudor isa_tudor_andrei Data 22 aprilie 2019 12:30:57
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 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 pas = 1<<20;
  int r = 0;
  while( pas > 0 ) {
    pas /= 2;
    if( r + pas < x && v[r+pas].dr <= v[x].st )
      r += pas;
  }
  return r;
}

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] = 0;
    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;
}