Cod sursa(job #220470)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 10 noiembrie 2008 22:49:27
Problema 1-sir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <stdio.h>

const int N_MAX = 33000;
const int MOD = 194767;

int nrmod[N_MAX];

int main()
{
	freopen("1-sir.in", "r", stdin);
#ifndef _SCREEN_
	freopen("1-sir.out", "w", stdout);
#endif

	int N, S;
	scanf("%d %d\n", &N, &S);
	S = (N * (N - 1) / 2) - S;
	if (S < 0) {
		printf("0\n");
		return 0;
	}

	int MAX = 0, fac, mx;
	nrmod[0] = 1;
	for (int j = N - 1; j >= 1; j --) {
		fac = 2 * (N - j);
		mx = MAX;
		for (int k = MAX; k >= 0; k --) {
			if (k + fac <= S) {
				nrmod[k + fac] += nrmod[k];
				nrmod[k + fac] %= MOD;
				if (k + fac > mx) mx = k + fac;
			}
		}

		MAX = mx;
	}

	printf("%d\n", nrmod[S]);
	
	return 0;
}