Cod sursa(job #2029824)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 30 septembrie 2017 15:09:34
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include <bits/stdc++.h>
#define Nmax (int)132e3+5
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int best[Nmax];
vector <int> intrv[Nmax];
int main()
{
    int n,lsh,rsh,Time_MAX=0,i,j;
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>lsh>>rsh;
        intrv[rsh].push_back(lsh);
        Time_MAX=max(Time_MAX,rsh);
    }
    for(i=1;i<=Time_MAX;i++)
    {
        best[i]=best[i-1];
        for(j=0;j<intrv[i].size();j++)
            best[i]=max(best[i],best[intrv[i][j]]+i-intrv[i][j]);
    }
    g<<best[Time_MAX];

    return 0;
}