Cod sursa(job #2106316)

Utilizator darkviper17Dark Viper darkviper17 Data 15 ianuarie 2018 16:47:45
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
vector <pair<int, int>>v;

const int N = 100001;

long long start, final, var, total=0, x[N], dp[N], k = 0;

int L = 16, n;

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>>start>>final;
    v.push_back(make_pair(final, start));
  }

  sort(v.begin(), v.end());

 for(i = 0; i < n; i++)
    x[++k] = v[i].first;
    
   //eliminare dubluri
   for(i = 2, j = 1; i <= k; 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] + 1;
    
    return 0;
     
}