Cod sursa(job #1194520)

Utilizator WyvernFMI Stanescu Leonard Wyvern Data 3 iunie 2014 23:54:17
Problema Diamant Scor 90
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Semestrul 2 Marime 1.19 kb
#include <stdio.h>

#define MAX 44100
#define MOD 10000

int N, M, S, Sm;
int m[2][MAX + MAX + 2];

#define m(i, j) m[i][j + MAX]

int main()
{
    freopen("diamant.in", "rt", stdin);
    freopen("diamant.out", "wt", stdout);
    scanf("%d %d %d", &N, &M, &S);
    Sm = (N * (N + 1) >> 1) * (M * (M + 1) >> 1);
    if (S < -Sm || S > Sm)
    {
        printf("0\n");
        return 0;
    }

    m(0, 0) = 1;
    int step = 0;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
        {
            step ^= 1;

            for (int S = -Sm; S <= Sm; S++)
            {
                m( step, S ) = m( 1 ^ step, S );

                if (S - i * j >= -Sm)
                {
                    m( step, S ) += m( 1 ^ step, S - i * j );
                    if (m( step, S ) >= MOD)
                        m( step, S ) -= MOD;
                }
                if (S + i * j <= Sm)
                {
                    m( step, S ) += m( 1 ^ step, S + i * j );
                    if (m( step, S ) >= MOD)
                        m( step, S ) -= MOD;
                }
            }
        }
    printf("%d\n", m(step, S));

    return 0;
}