Cod sursa(job #2111617)

Utilizator darkviper17Dark Viper darkviper17 Data 22 ianuarie 2018 14:22:03
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

const int N = 100001;

pair<long long, long long> v[N];

long long n, x[N], dp[N], k;

long long L = 16;

int binary_search(long long y)
{
  int pas, r=0;
  pas = 1 << L;

  while(pas)
  {
    if(x[r + pas] <= y && r + pas <= k) r+=pas;

      pas/=2;
  }
  return r;
}

int main()
{
  int i, j;

  fin>>n;

  for(i=1; i<=n; i++)
  {
    fin >> v[i].second >> v[i].first;
    x[i] = v[i].first;
  }
   
  sort(x + 1, x + n + 1); 
  sort(v + 1, v + n + 1);

   //eliminare dubluri
   for(i = 2, j = 1; i <= n; i++)
   {
     if(x[i] != x[i - 1]) x[++j] = x[i];
   }

   k = j;


    for(int i = 1; i <= n; i++){

        long long st=binary_search(v[i].second);

        long long dr=binary_search(v[i].first);

        dp[dr]=max(dp[dr], dp[st]-v[i].second + v[i].first);

        dp[dr]=max(dp[dr],dp[dr-1]);
    }

    fout << dp[k] ;

    return 0;

}