Cod sursa(job #1692223)

Utilizator isa_tudor_andreiAndrei Tudor isa_tudor_andrei Data 20 aprilie 2016 14:58:19
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <cstdio>
#include <algorithm>

using namespace std;

int n;

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

int d[100001];

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

int maxi(int a,int b) {
  if( a < b )
      a = b;
  return a;
}

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

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