Pagini recente » Cod sursa (job #1093032) | Cod sursa (job #1483742) | Cod sursa (job #1118464) | Cod sursa (job #1418981) | Cod sursa (job #2855744)
// Obs: O suma cu i elemente o construiesc in functie de primul semn
// primul semn il adaug la solutiile anterioare, iar acesta imi afecteaza solutia cu i-1 (+ sau -, in functie de semnul ales)
// de aici iese recurenta
#include <bits/stdc++.h>
using namespace std;
ifstream fin("1-sir.in");
ofstream fout("1-sir.out");
const int NMAX = 300, MOD = 194767;
int dp[2][NMAX * NMAX]; // dp[i][j] - cate sume de i elemente am, suma si suma j
inline void swapLines()
{
int i;
for(i = 0; i < NMAX * NMAX; ++i)
dp[0][i] = dp[1][i];
}
int main()
{
int n, s;
fin >> n >> s;
s = abs(s);
if(s > n * (n + 1) / 2)
{
fout << "0";
return 0;
}
int current = 0;
int lcurent, sumMax = n * (n + 1) / 2, sumCurrent;
dp[current][0] = 1;
for(lcurent = 2; lcurent <= n; ++lcurent)
{
current = 1 - current;
//swapLines();
for(sumCurrent = 0; sumCurrent <= sumMax; ++sumCurrent)
{
dp[current][sumCurrent] = dp[1-current][sumCurrent + lcurent - 1] + dp[1-current][abs(sumCurrent - lcurent + 1)];
if(dp[current][sumCurrent] >= MOD)
dp[current][sumCurrent] -= MOD;
}
}
fout << dp[current][s];
return 0;
}