Cod sursa(job #2750673)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 12 mai 2021 18:49:40
Problema 1-sir Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 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)
{	
	const int smax = 70000;
	const int dep = 35000;
	int dp[smax][2];
	memset(dp, 0, sizeof(dp));
	
	dp[dep][0] = 1;
	int nxt = 1;
	int smaxim = (N * (N - 1)) / 2;
	if(abs(S) > smaxim)
		return 0;
	for(int i = 2;i <= N;++i)
	{
		for(int j = -smaxim;j <= smaxim;++j)
		{
			dp[j + dep][nxt] = dp[j - i + 1 + dep][nxt ^ 1] + dp[j + i - 1 + dep][nxt ^ 1];
			dp[j + dep][nxt] %= mod;
		}
		nxt ^= 1;
	}
	return dp[S + dep][nxt ^ 1];
}
 
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;
}