Cod sursa(job #2505571)

Utilizator Ykm911Ichim Stefan Ykm911 Data 7 decembrie 2019 00:45:23
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <bits/stdc++.h>
#define NMax 100005

using namespace std;

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

struct Concert
{
    int st, dr, timp;
};

int n, dp[NMax];
Concert Interval[NMax];

inline bool Sortare(Concert x, Concert y)
{
    return (x.dr < y.dr);
}


void Citire()
{
    int i;
    fin >> n;
    for(i = 1; i <= n; i++)
    {
        fin >> Interval[i].st >> Interval[i].dr;
        Interval[i].timp = Interval[i].dr - Interval[i].st;
    }
    sort(Interval + 1, Interval + n + 1, Sortare);
}

int CautareBinara(int x, int capat)
{
    int st = 1, dr = capat, sol = 0, mij;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(Interval[mij].dr <= x)
        {
            sol = mij;
            st = mij + 1;
        }
        else dr = mij - 1;
    }
    return sol;
}

void Rezolvare()
{
    for(int i = 1; i <= n; i++)
        dp[i] = max(dp[CautareBinara(Interval[i].st, i - 1)] + Interval[i].timp, dp[i - 1]);
    fout << dp[n];
    fin.close();
    fout.close();
}

int main()
{
    Citire();
    Rezolvare();
    return 0;
}