Cod sursa(job #3224293)

Utilizator BiceaToader David Stefan Bicea Data 15 aprilie 2024 08:55:47
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("heavyetal.in");
ofstream g("heavymetal.out");
int n,p,u,m,s,k,ok,e[1000001],ans;
struct kol
{
    int a,b;
}v[1000001];
int cmp(kol a,kol b)
{
    return (a.b<b.b || a.b==b.b && a.a<b.a);
}
int main()
{p=1;u=n,ans=0;
  f>>n;
for(int i=1;i<=n;i++)
f>>v[i].a>>v[i].b;
    sort(v+1,v+n+1,cmp);
 for (int i=1;i<=n;i++)
    {

        while (p<=u)
        {
            int m=(p+u)/2;
            if (v[m].b<=v[i].a) p=m+1,ans=m;
            else u=m-1;
        }
        e[i]=max(e[i-1],e[ans]+v[i].b-v[i].a);

    }
    g<<e[n];
    return 0;
}