Cod sursa(job #2750668)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 12 mai 2021 18:39:26
Problema 1-sir Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <iostream>
#include <cstring>
#include <fstream>
#include <map>
#include <cmath>
#include <unordered_map>
using namespace std;

const int mod = 194767;

int solve(int S, int N)
{	
	int smaxim = (N * (N - 1)) / 2;
	if(abs(S) > smaxim)
		return 0;
	int smax = 2 * smaxim + 3;
	int dep = smaxim;
	dp1[dep] = 1;
	
	int dp1[smax], dp2[smax];
	memset(dp1, 0, sizeof(dp1));
	memset(dp2, 0, sizeof(dp2));
	for(int i = 2;i <= N;++i)
	{
		for(int j = -smaxim;j <= smaxim;++j)
		{
			if(abs(j - i + 1) <= smaxim)
				dp2[j + dep] += dp1[j - i + 1 + dep];
			if(abs(j + i - 1) <= smaxim)
				dp2[j + dep] += dp1[j + i - 1 + dep];
			dp2[j + dep] %= mod;
		}
		for(int j = -smaxim;j <= smaxim;++j)
			dp1[j + dep] = dp2[j + dep];
	}
	return dp1[S + dep];
}

int main() {
	ifstream in("1-sir.in");
	ofstream out("1-sir.out");
	int N, S;
	
	in >> N >> S;
	out << solve(S, N) << "\n";
	in.close();
	out.close();
	return 0;
}