Cod sursa(job #341337)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 18 august 2009 10:30:03
Problema Diamant Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <stdio.h>
#include <string.h>
#define N 21
#define P 1<<17
#define NR 10000
int n,m,x;
int v[N*N],r,sum;
int comb[P],comb2[P];
char marc[P],marc2[P];
void matrice()
{
	int i,j;
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++)
		{
			v[++r]=i*j;
			sum+=i*j;
		}
}
void dinamica()
{
	int i,j,t;
	marc[sum]=1;
	comb[sum]=1;
	for (i=1; i<=r; i++)
	{
		memcpy(marc2,marc,sizeof(marc));
		memcpy(comb2,comb,sizeof(comb));
		for (j=-sum; j<=sum; j++)
			if (marc2[j+sum])
			{
				marc[j+sum-v[i]]=1;
				marc[j+sum+v[i]]=1;
				comb[j+sum-v[i]]+=comb2[j+sum];
				comb[j+sum+v[i]]+=comb2[j+sum];
				if (comb[j+sum-v[i]]>NR)
				{
					t=comb[j+sum-v[i]];
					comb[j+sum-v[i]]=t-(t/NR*NR);
				}
				if (comb[j+sum+v[i]]>NR)
				{
					t=comb[j+sum+v[i]];
					comb[j+sum+v[i]]=t-(t/NR*NR);
				}
			}
	}
	printf("%d\n",comb[x+sum]);
}
int main()
{
	freopen("diamant.in","r",stdin);
	freopen("diamant.out","w",stdout);
	scanf("%d%d%d",&n,&m,&x);
	matrice();
	if (sum<x)
		printf("0\n");
	else
		dinamica();
	return 0;
}