Cod sursa(job #2540799)

Utilizator serafimalex2001Serafim Alex serafimalex2001 Data 7 februarie 2020 18:55:51
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

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

struct band{
    int s,d,t;
}a[100009];

int n;

bool comp(band a, band b)
{
    return a.d < b.d || a.d == b.d && a.s < b.s;
}

void Read()
{
    int i,j;
    int vmax = 0;
    int dr, st, poz, mid;
    fin>>n;
    for(i=1; i<=n; ++i)
    {
        fin>>a[i].s>>a[i].d;
    }
    sort(a+1, a+n+1, comp);
    a[1].t = a[1].d - a[1].s;
    for(i=2; i<=n; ++i)
    {
        a[i].t = a[i-1].t;
        st = 1;
        dr = i;
        poz = 0;
        while(st<=dr)
        {
            mid = (st+dr)/2;
            if(a[mid].d <= a[i].s)
            {
                poz = mid;
                st = mid+1;
            }
            else dr = mid-1;
        }
        a[i].t =max(a[i].t, a[poz].t + (a[i].d - a[i].s));
    }
    for(i=1; i<=n; ++i)
        if(a[i].t > vmax)
            vmax = a[i].t;
    fout<<vmax;
}

int main()
{
    Read();
    return 0;
}