Cod sursa(job #2515971)

Utilizator miruna1224Floroiu Miruna miruna1224 Data 29 decembrie 2019 21:33:38
Problema Heavy metal Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>
#include <algorithm>
#include <cmath>


#define ll long long
#define N 100005


using namespace std;


ll a, b, mij, n, dp[N];
pair<int, int> v[N];


ll max ( ll a, ll b){
  if ( a > b )
    return a;
  else return b;
}


int main(){


    ifstream in ("heavymetal.in");

    in >> n;
    for (int i = 1; i <= n; i++)
      in >> v[i].second >> v[i].first;
    sort (v + 1, v + n + 1);
    for (int i = 1; i <= n; i++ )
      swap (v[i].first, v[i].second);

    in.close();


    ofstream out ("heavymetal.out");

    dp[1] = v[1].second - v[1].first;
    for (int i = 2; i <= n; i++ ){
      dp[i] = dp[i - 1];
      dp[i] = max (dp[i], v[i].second - v[i].first);
      a = 1;
      b = i - 1;
      while ( a <= b ){
          mij = ( a + b ) / 2;
          if ( v[mij].second <= v[mij].first )
            a = mij + 1;
          else
            b = mij - 1;
      }
      dp[i] = max( dp[i], dp[b] + v[i].second - v[i].first);
    }

    out << dp[n];

    out.close();


    return 0;
}