Cod sursa(job #2515972)

Utilizator miruna1224Floroiu Miruna miruna1224 Data 29 decembrie 2019 21:36:50
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 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[i].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;
}