Cod sursa(job #3284152)

Utilizator luc3lexa_Alexandrescu Luca luc3lexa_ Data 11 martie 2025 10:34:28
Problema 1-sir Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("1-sir.in");
ofstream fout("1-sir.out");

const int nmax = 260;
const int summax = 4e4;
const int MOD = 194767;

int n,s,maximum_sum;
vector<vector<int>> dp(2,vector<int> (2*summax + 10,0));

void read_input(){
	fin >> n >> s;
};

void solve(){
	maximum_sum = n*(n+1)/2;
	dp[0][summax] = 1;
	int state = 0;
	for(int i = 2; i <= n; i++,state^=1){
	
		int limita = i*(i-1)/2;
		fill(dp[state^1].begin(),dp[state^1].begin() + 1 + summax*2,0);
		
		for(int j = -limita; j <= limita; j++){
			if(j + (i-1) <= summax){dp[state^1][j + (i-1) + summax] = (dp[state^1][j + (i-1) + summax] + dp[state][j + summax])%MOD;}
			if(j - (i-1) >= -summax){dp[state^1][j - (i-1) + summax] = (dp[state^1][j - (i-1) + summax] + dp[state][j + summax])%MOD;};
		}
	};
	fout << dp[state][s + summax]%MOD;
}
int main(){
	read_input();
	solve();
	return 0;
}