Cod sursa(job #3130782)

Utilizator Roxana_3Asavei Roxana Roxana_3 Data 18 mai 2023 16:27:24
Problema Heavy metal Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <bits/stdc++.h>
#define N 100000
using namespace std;

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

struct concert
{
    int st;
    int dr;
} a[N + 5];
int n;

long long timp_max[N + 5]; /// timp_max[i] = timpul maxim in care se canta daca aleg concertul i
long long timp_final[N + 5]; /// timp_final[i] = ora la care se termina interv maxim in care se canta daca aleg concertul i
/// clar o sa fie cresc

void Citire()
{
    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> a[i].st >> a[i].dr;
}

inline bool comp(concert x, concert y) /// sortam cresc dupa capatul din dreapta
{
    return x.dr < y.dr || (x.dr == y.dr && x.st < y.st);
}


void Rezolvare()
{
    timp_max[1] = a[1].dr - a[1].st;
    timp_final[1] = a[1].dr;

    for(int i = 2; i <= n; ++i)
    {
        timp_max[i] = a[i].dr - a[i].st; /// presupun ca nu pot sa l adaug nicaieri
        timp_final[i] = a[i].dr;
        /// caut pozitia pt care timp_final[x] <= a[i].st && timp_max[x] este maxim
        int M = -1;
        for(int j = 1; j < i; ++j)
            if(timp_final[j] <= a[i].st && timp_max[j] > M) M = timp_max[j];
        if(M != -1)
            timp_max[i] += M;
    }

    long long sol = -1;
    for(int i = 1; i <= n; ++i)
        sol = max(sol, timp_max[i]);
    fout << sol;
}

int main()
{
    Citire();
    sort(a + 1, a + n  + 1, comp);
    Rezolvare();

    return 0;
}