Cod sursa(job #3326398)

Utilizator GavrilitaIanisGavrilita Ianis GavrilitaIanis Data 28 noiembrie 2025 18:04:05
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

int dp[100005], n;

struct concert
{
    int start, finall;
}c[100005];

bool cmp(concert A, concert B)
{
    if(A.finall < B.finall)
        return 1;
    else if(A.finall > B.finall)
        return 0;
    else
    {
        if(A.start < B.start)
            return 1;
        else
            return 0;
    }
}

int cb(int st, int dr, int x)
{
    int mij, poz = -1;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(c[mij].finall <= x)
        {
            poz = mij;
            st = mij + 1;
        }
        else if(c[mij].finall > x)
            dr = mij - 1;
    }
    return poz;
}

int main()
{
    int i, j;
    fin >> n;
    for(i = 1; i <= n; i++)
        fin >> c[i].start >> c[i].finall;
    sort(c + 1, c + n + 1, cmp);
    for(i = 1; i <= n; i++)
    {
        j = cb(1, i - 1, c[i].start);
        dp[i] = max(dp[i-1], c[i].finall - c[i].start + dp[j]);
    }
    fout << dp[n];
    return 0;
}