Cod sursa(job #2282939)

Utilizator PredescuSebastianIonPredescu Sebastian Ion PredescuSebastianIon Data 14 noiembrie 2018 19:20:28
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct ceva
{
    int x,y;
} a[100002];
int sol[100002],n;
bool cmp(ceva x,ceva y)
{
    return x.y<y.y;
}
int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
    {
        f>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1,cmp);
    sol[1]=a[1].y-a[1].x;
    for(int i=2;i<=n;i++)
    {
        int st=1,poz=0,dr=i-1;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(a[i].x>=a[mij].y)
            {
                st=mij+1;
                poz=mij;
            }
            else
            {
                dr=mij-1;
            }
        }
        sol[i]=max(sol[i-1],sol[poz]+a[i].y-a[i].x);
    }
    g<<sol[n]<<'\n';
    return 0;
}