Cod sursa(job #2511578)

Utilizator lucianistratiIstrati Lucian lucianistrati Data 19 decembrie 2019 12:42:58
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#include <map>
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define pll pair<long,long>
#define pdd pair<double,double>
//#define first f
//#define second s
#define INF 1e9
#define MOD 1e9+7
using namespace std;
int N,i,j,k,ans;
int dp[100010];
vector<pair<int,int> > v(100010);
int cautare_binara_1(int x,int l,int r)
{
   int mij,pos=-1;
    while(l<=r)
    {
        mij=(l+r)/2;
        if (v[mij].second<=x)
        {
            pos=mij;
            l=mij+1;
        }
        else
        {
            r=mij-1;
        }
    }
    return pos;
}
bool cmp(const pair<int,int> & a,const pair<int,int> & b)
{
    if(a.second!=b.second)
    return (a.second<b.second);
    else
    return (a.first<b.first);
}
//dp[i] - cel mai bun cost din primele i spectacole sortate dupa capatul din dreata, in care il scoatem si pe i
//dp[i] = max(dp[i-1],y[i]-x[i]+dp[j]) unde j e cel mai mare index astfel incat y[index] mai mic decat x[i]
int main()
{

    ifstream fin("heavymetal.in");
    ofstream fout("heavymetal.out");
     fin>>N;
    v = vector<pair<int, int>> (N + 1);

    v[0].first=-1;
    v[0].second=-1;
    for(i=1;i<=N;i++)
    {
        fin>>v[i].first>>v[i].second;
    }
    sort(v.begin(),v.end(),cmp);
    for(i=1;i<=N;i++)
    {
        k=cautare_binara_1(v[i].first,0,i-1);
        dp[i]=max(dp[i-1],v[i].second-v[i].first+dp[k]);
    }
//    for(i=0;i<=N;i++)
//    {
//        cout<<dp[i]<<' ';
//    }
    fout<<dp[N];
    fin.close();
    fout.close();
    return 0;
}