Cod sursa(job #2587954)

Utilizator armigheGheorghe Liviu Armand armighe Data 23 martie 2020 21:11:20
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
///SLIPKNOT PSYCHOSOCIAL
//the best band and the best song
#include<fstream>
#include<algorithm>
using namespace std;
ifstream heavy("heavymetal.in");
ofstream metal("heavymetal.out");
struct elem
{
    int x,y,heavymetal;
};
elem v[100002];

inline bool cmp(const elem &a,const elem &b)
{
    return a.y<b.y;
}

int n,w[200002],slipknot[200002];

int SLIPKNOT(int x)
{
    int st=1,dr=2*n,mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(x<=w[mij])
            dr=mij-1;
        else
            st=mij+1;
    }
    return dr+1;
}

int main()
{
    int i,k=1;
    heavy>>n;
    for(i=1;i<=n;i++)
    {
        heavy>>v[i].x>>v[i].y;
        v[i].heavymetal=v[i].y-v[i].x;
        w[2*i-1]=v[i].x;
        w[2*i]=v[i].y;
    }
    sort(w+1,w+2*n+1);
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;i++)
    {
        v[i].x=SLIPKNOT(v[i].x);
        v[i].y=SLIPKNOT(v[i].y);
    }
    for(i=1;i<=n;i++)
    {
        while(k<=v[i].y)
            slipknot[k]=max(slipknot[k],slipknot[k-1]),k++;
        slipknot[v[i].y]=max(slipknot[v[i].y],slipknot[v[i].x]+v[i].heavymetal);
    }
    metal<<slipknot[v[n].y];
    return 0;
}