Cod sursa(job #2930073)

Utilizator Theo14Ancuta Theodor Theo14 Data 27 octombrie 2022 14:16:41
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<bits/stdc++.h>
#define int long long
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");

int n,v[200005],k,con,nou[200005],dp[200005];///dp[i]=timpul maxim pana la momentul i

struct elem
{
    int x,y,t;
}w[100005];

int cmp(elem a, elem b)
{
    return a.y<b.y;
}

int caut_bin(int x)
{
    int st=1,dr=con,retin;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(x==nou[mij])
        {
            retin=mij;
            break;
        }
        if(x<nou[mij])
            dr=mij-1;
        else
            st=mij+1;
    }
    return retin;
}

signed main()
{
    int i,x,y;
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>x>>y;
        k++;
        v[k]=x;
        k++;
        v[k]=y;
        w[i].x=x;
        w[i].y=y;
        w[i].t=w[i].y-w[i].x;
    }
    sort(w+1,w+n+1,cmp);
    sort(v+1,v+k+1);
    for(i=1;i<=k;i++)
    {
        con++;
        nou[con]=v[i];
        while(i+1<=k && v[i+1]==v[i])
            i++;
    }
    for(i=1;i<=n;i++)
        w[i].x=caut_bin(w[i].x),w[i].y=caut_bin(w[i].y);
    dp[0]=0;
    k=1;
    for(i=1;i<=n;i++)
    {
        while(k<w[i].y)
        {
            dp[k]=max(dp[k],dp[k-1]);
            k++;
        }
        dp[k]=max(dp[k],dp[k-1]);
        if(k==w[i].y)
            dp[k]=max(dp[k],dp[w[i].x]+w[i].t);
        k++;
    }
    g<<dp[k-1];
    return 0;
}