Cod sursa(job #2397866)

Utilizator vlad.ulmeanu30Ulmeanu Vlad vlad.ulmeanu30 Data 4 aprilie 2019 20:24:20
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define maxn 100000

using namespace std;

pii v[maxn+5];
pii dp[maxn+5]; ///dp[i]-timp maxim cu bandele 0..i (fi) capat dreapta (se)

bool cmp ( pii a, pii b )
{
  if ( a.fi != b.fi ) return a.fi < b.fi;
  return a.se > b.se;
}

int main ()
{
  ifstream fin ( "heavymetal.in" );
  ofstream fout ( "heavymetal.out" );

  int n; fin >> n;

  int i, j, z, itv, _M = 0, pas;
  for ( i = 0; i < n; i++ ) fin >> v[i].fi >> v[i].se;
  sort ( v, v + n, cmp );

  for ( i = 0; i < n; i++ )
  {
    itv = v[i].se-v[i].fi;
    dp[i] = {itv,v[i].se};
    for ( j = 0, pas = (1<<20); pas > 0; pas /= 2 )
      if ( j + pas <= i && dp[j+pas].se <= v[i].fi && dp[i].fi < dp[j+pas].fi + itv ) j += pas;
    dp[i] = {dp[j].fi + itv,v[i].se};
    _M = max(_M, dp[i].fi);
  }

  fout << _M;

  fin.close ();
  fout.close ();

  return 0;
}