Cod sursa(job #157865)

Utilizator M@2Te4iMatei Misarca M@2Te4i Data 13 martie 2008 12:26:41
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <cstdio>
#include <vector>

using namespace std;

vector <int> w,q,b;
int n,m;

void citire()
{
    freopen("heavymetal.in","r",stdin);
    scanf("%d", &n);
    int a,s;
    m=0;
    w.push_back(0);
    q.push_back(0);
    for (int i=1; i<=n; i++)
    {
        scanf("%d%d", &a, &s);
        w.push_back(a);
        q.push_back(s);
        if (s>m)
            m=s;
    }
    fclose(stdin);
}

void rezolvare()
{
    b.push_back(0);
    for (int i=1; i<=m; i++)
    {
        b.push_back(b[i-1]);
        for (int j=1; j<=n; j++)
            if (q[j]==i)
                if (b[i]<b[w[j]]+(q[j]-w[j]))
                    b[i]=b[w[j]]+(q[j]-w[j]);
    }
}

int main()
{
    citire();
    rezolvare();
    freopen("heavymetal.out","w",stdout);
    printf("%d\n",b[m]);
    fclose(stdout);
    return 0;
}