Cod sursa(job #2561799)

Utilizator AlexDontuAlex Dontu AlexDontu Data 29 februarie 2020 10:14:31
Problema Heavy metal Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");
int n,i,a,b,maxi,s[100001],j;
struct duten_pula_mea_de_ghinda {int start,finish,length;}v[100001];

int compare (duten_pula_mea_de_ghinda a, duten_pula_mea_de_ghinda b)
{
    return a.finish<b.finish||a.finish==b.finish&&a.start<=b.start;
}

int main()
{
    fin>>n;
    for (i=1;i<=n;i++)
    {
        fin>>v[i].start>>v[i].finish;
        v[i].length=v[i].finish-v[i].start;
    }
    sort (v+1,v+n+1,compare);
    for (i=n;i>=1;i--)
    {
        s[i]=v[i].length;
        for (j=i+1;j<=n;j++)
        {
            if (v[i].finish<=v[j].start&&s[i]<=s[j]+v[i].length)
            {
                s[i]=s[j]+v[i].length;
            }
        }
        if (s[i]>maxi)
            maxi=s[i];
    }
    fout<<maxi;
    return 0;
}