Cod sursa(job #2046811)

Utilizator KemyKoTeo Virghi KemyKo Data 24 octombrie 2017 09:53:01
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define NMAX 100001

using namespace std;

ifstream f("heavymetal.in");
ofstream g("heavymetal.out");

int n,fv[NMAX],tmx,rez[NMAX];
struct metal
{
    int st,dr;
}v[NMAX];

void citire()
{
    int i;
    f>>n;
    for (i=1;i<=n;i++){
        f>>v[i].st>>v[i].dr;
        if (v[i].dr>tmx)
            tmx=v[i].dr;
    }
}

int comp(metal a,metal b)
{
    if (a.dr == b.dr)
        return (a.st < b.st);
    return (a.dr < b.dr);
}

void afis()
{
    int i,k,j;
    for (i=1;i<=tmx;i++){
        rez[i]=rez[i-1];
        for (j=1;j<=n;j++)
            if(v[j].dr==i)
                rez[i]=max(rez[i], rez[v[j].st]+ (v[j].dr - v[j].st));
    }
    g<<rez[tmx];
}

int main()
{
    citire();
    sort(v+1,v+1+n,comp);
    afis();
    return 0;
}