Cod sursa(job #3318261)

Utilizator alexiabortunBortun Alexia alexiabortun Data 27 octombrie 2025 18:41:03
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

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

#define N 100001
struct concert
{
    int start, finish;
}a[N];
int n, pd[N], t[N];
void citire()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> a[i].start >> a[i].finish;
}
bool cmp(concert x, concert y)
{
    return x.finish < y.finish;
}
void timp()
{
    for(int i = 1; i <= n; i++)
        t[i] = a[i].finish - a[i].start;
}
int cb(int i)
{
    int st = 1, dr = i - 1, rez = 0;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(a[mij].finish <= a[i].start)
        {
            rez = mij; // mij este candidat valid
            st = mij + 1;
        }
        else
            dr = mij - 1;
    }
    return rez;
}

void dp()
{
    pd[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        int j = cb(i);
        pd[i] = max(pd[i - 1], t[i] + pd[j]);
    }
}
int main()
{
    citire();
    sort(a + 1, a + n + 1, cmp);
    /*for(int i = 1; i <= n; i++)
        fout << a[i]. start << " " << a[i].finish << "\n";*/
    timp();
    dp();
    fout << pd[n];
    return 0;
}