Cod sursa(job #3224275)

Utilizator BalanelBalan Stefan Balanel Data 15 aprilie 2024 08:29:25
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<bits/stdc++.h>
#define int long long
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
int n,d[100001],mx=-1;
struct form {
    int x,y;
}v[100001];
bool comp(form a, form b) {
    if(a.y==b.y) return a.x<b.x;
    return a.y<b.y;
}
int32_t main()
{in>>n;
for(int i=1;i<=n;++i)
    in>>v[i].x>>v[i].y;
sort(v+1,v+n+1,comp);
d[1]=v[1].y-v[1].x;
for(int i=2;i<=n;++i) {
    int st=1,dr=i,sol=0;
    while(st<=dr) {
        int mij=(st+dr)/2;
        if(v[mij].y<=v[i].x) st=mij+1,sol=mij;
                else dr=mij-1;
        }
    d[i]=max(d[i-1],v[i].y-v[i].x+d[sol]);
    }
out<<d[n];
return 0;
}