Cod sursa(job #630565)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 5 noiembrie 2011 20:09:25
Problema Plus Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <cstdio>

#define SMax 300005

using namespace std;

int N[3], V[3], Sum, SumMin, SumMax;
long long S[2][2*SMax+2], SL[2][2*SMax+2], SR[2][2*SMax+2];

void Read ()
{
    freopen ("plus.in", "r", stdin);
    scanf ("%d", &Sum);
    for (int i=0; i<3; ++i)
    {
        scanf ("%d %d", &N[i], &V[i]);
        if (V[i]==-1)
        {
            SumMin-=N[i];
        }
        if (V[i]==1)
        {
            SumMax+=N[i];
        }
    }
}

void Print ()
{
    freopen ("plus.out", "w", stdout);
    printf ("%lld\n", S[0][Sum+SMax]);
}

void Initialize ()
{
    S[0][SMax]=1;
    for (int s=SumMin; s<=0; ++s)
    {
        SR[0][s+SMax]=1;
    }
    for (int s=0; s<=SumMax; ++s)
    {
        SL[0][s+SMax]=1;
    }
}

void Solve ()
{
    Initialize ();
    int l=1;
    for (int i=0; i<3; ++i, l^=1)
    {
        for (int s=SumMin; s<=SumMax; ++s)
        {
            S[l][s+SMax]=SL[l][s+SMax]=SR[l][s+SMax]=0;
        }
        for (int s=SumMin; s<=SumMax; ++s)
        {
            if (V[i]==-1)
            {
                S[l][s+SMax]=SR[l^1][s+SMax]-SR[l^1][s+SMax+N[i]+1];
            }
            if (V[i]==0)
            {
                S[l][s+SMax]=S[l^1][s+SMax]*(N[i]+1);
            }
            if (V[i]==1)
            {
                S[l][s+SMax]=SL[l^1][s+SMax]-SL[l^1][s+SMax-N[i]-1];
            }
        }
        for (long long s=SumMin; s<=SumMax; ++s)
        {
            SL[l][s+SMax]=S[l][s+SMax]+SL[l][s+SMax-1];
        }
        for (long long s=SumMax; s>=SumMin; --s)
        {
            SR[l][s+SMax]=S[l][s+SMax]+SR[l][s+SMax+1];
        }
    }
    S[0][Sum+SMax]=S[l^1][Sum+SMax];
}

int main()
{
    Read ();
    Solve ();
    Print ();
    return 0;
}