Cod sursa(job #2104439)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 11 ianuarie 2018 17:57:45
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <bits/stdc++.h>
#define st first
#define dr second
using namespace std;
pair <int,int> v[100001];
int tmax[100001];
int bs(int k,int x)
{
    int rez,pas;
    pas=1<<17;
    rez=0;
    while(pas)
    {
        if(rez+pas<k && v[rez+pas].dr<=x)
            rez+=pas;
        pas/=2;
    }
    return rez;
}
int main()
{
    int i,n,pos;
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    scanf("%d",&n);
    for(i=1; i<=n; i++)
        scanf("%d%d",&v[i].st,&v[i].dr);
    sort(v+1,v+n+1,[](pair<int,int> a,pair<int,int> b){return a.dr<b.dr;});
    for(i=1; i<=n; i++)
    {
        pos=bs(i,v[i].st);
        tmax[i]=max(tmax[i-1],tmax[pos]+v[i].dr-v[i].st);
    }
    printf("%d\n",tmax[n]);

    return 0;
}