Cod sursa(job #3131120)

Utilizator Roxana_3Asavei Roxana Roxana_3 Data 19 mai 2023 12:02:47
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.82 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 din primele i concerte
int timp_final[N + 5]; /// timp_final[i] = ora la care se termina daca alaeg timpul maxim  din primele i

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);
}

int CB(int st, int dr, int x)
{
    /// cautam cea mai din dreapta pozitie pt care timp_final[i] <= a[i].st (x)
    int possible = 0;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(timp_final[mij] <= x) possible = mij, st = mij + 1;
        else dr = mij - 1;
    }

    return possible;
}


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


    for(int i = 2; i <= n; ++i)
    {
        /// daca pot sa l alatur celelorlate concerte, o fac NU NEAPARAT, POATE E MAI AVANTAJOS SA NU O FAC
        int p = CB(1, i - 1, a[i].st); /// caut in cele ant cea mai din dreapta poz pt care timp_final[i] <= a[i].st
        int timp_curent = a[i].dr - a[i].st;

        if(timp_max[p] + timp_curent > timp_max[i - 1])
        {
            timp_max[i] = timp_max[p] + timp_curent;
            timp_final[i] = a[i].dr;
        }

        else
        {
            timp_max[i] = timp_max[i - 1];
            timp_final[i] = timp_final[i - 1];
        }

    }

    fout << timp_max[n];
}

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

    return 0;
}