Cod sursa(job #3224289)

Utilizator Silviu643Dumitrescu Silviu Florian Silviu643 Data 15 aprilie 2024 08:50:05
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct timpu
{
    int s,d;
}a[100005];
bool fcmp(timpu x, timpu y)
{
    if(x.d>y.d) return 0;
    return 1;
}
int n,v[100005],mx;
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>a[i].s>>a[i].d;
    sort(a+1,a+n+1,fcmp);
    for(int i=1;i<=n;i++)
    {
        int x=a[i].s;
        while(v[x]==0 && x>0)
            x--;
        int y=a[i].d;
        while(v[y]==0 && y>0)
            y--;
        v[a[i].d]=max(v[x]+(a[i].d-a[i].s),v[y]);
        if(mx<v[a[i].d]) mx=v[a[i].d];
    }
    fout<<mx;
    return 0;
}