Cod sursa(job #3224296)

Utilizator Lupu_Daniel_24Lupu Daniel Lupu_Daniel_24 Data 15 aprilie 2024 09:02:04
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int n;
int timp[100005],ans;
struct concert
{
    int p,u;
} v[100005];
int comp(concert a, concert b)
{
    if(a.u==b.u) return a.p<b.p;
    else return a.u<b.u;
}
int caut(int x)
{
    int m,p=1,u=n;
    while (p<=u)
    {
        int m=(p+u)/2;
        if (v[m].u<=v[x].p) p=m+1;
        else u=m-1;
    }
    return u;
}
void dp()
{
    int i,j;
    for(i=1; i<=n; i++)
    {
        j=caut(i);
        timp[i]=max(timp[i-1],timp[j]+v[i].u-v[i].p);
        ans=max(ans,timp[i]);
    }
    g<<ans;
}
int main()
{
    f>>n;
    for(int i=1; i<=n; i++)
        f>>v[i].p>>v[i].u;
    sort(v+1,v+n+1,comp);
    dp();

    return 0;
}