Cod sursa(job #911154)

Utilizator ELHoriaHoria Cretescu ELHoria Data 11 martie 2013 13:01:07
Problema 1-sir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <fstream>

using namespace std;

ifstream cin("1-sir.in");
ofstream cout("1-sir.out");

const int mod = 194767, SMAX = 1<<15;
inline void getMod(int &val){ val -= val < mod ? 0 : mod;}
int N, S;
int dp[2][SMAX];


int solve() {
	if(S > N*(N - 1)/2) return 0;
	dp[0][0] = 1;
	const int SUM = N*(N - 1)/2;
	int line = 0;
	for(int i = 1;i < N;i++,line = 1 - line) {
		for(int j = 0;j <= SUM;j++) {
			dp[1 - line][j] = dp[line][j + i] + dp[line][j - i < 0 ? i - j : j - i];
			getMod(dp[1 - line][j]);
		}
	}
	return dp[line][S];
}

int main()
{
	cin>>N>>S;
	if(S < 0) S = -S;
	cout<<solve()<<"\n";
	return 0;
}