Cod sursa(job #2769517)

Utilizator Raresr14Rosca Rares Raresr14 Data 16 august 2021 14:24:14
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <bits/stdc++.h>
#define Y first
#define X second.first
#define V second.second
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int i,maxim,n,j,st,dr,mid,D[100010];
pair<int,pair<int,int>> v[100010];
int main(){
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i].X>>v[i].Y,v[i].V=v[i].Y-v[i].X;
    sort(v+1,v+n+1);
    D[1]=v[1].V;
    for(i=2;i<=n;i++){
        D[i]=D[i-1];
        if(v[i].X>=v[i-1].Y){
            D[i]=D[i-1]+v[i].V;
        }else{
           st=1;
           dr=i-2;
           while(st<=dr){
                mid=(st+dr)/2;
                if(v[i].X>=v[mid].Y)
                    st=mid+1;
                else
                    dr=mid-1;
           }
           D[i]=max(D[i],D[dr]+v[i].V);

        }
    }
    fout<<D[n];
    return 0;
}