Cod sursa(job #2600299)

Utilizator Rares5000Baciu Rares Rares5000 Data 12 aprilie 2020 13:29:58
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;

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

struct intervale
{
    int beg, endd, dif;
}p[100002];

int n;

int poz[100002];

int cmp(intervale A, intervale B)
{
    if(A.beg < B.beg)
        return 1;
    else if(A.beg == B.beg)
        if(A.endd < B.endd) return 1;
    return 0;
}

int main()
{
    int i, j;
    fin >> n;
    for(i = 1; i <= n; i++)
    {
        fin >> p[i].beg >> p[i].endd;
        p[i].dif = p[i].endd - p[i].beg;
    }
    sort(p + 1, p + n + 1, cmp);
    for(i = 1; i <= n; i++)
        for(j = 1; j < i; j++)
            if(p[j].endd < p[i].beg)
            {
                if(p[j].dif + p[i].dif > p[i].dif)
                    p[i].dif = p[j].dif + p[i].dif;
            }
    int maxim = 0;
    for(i = 1; i <= n; i++)
        maxim = max(maxim, p[i].dif);
    fout << maxim;
    return 0;
}