Mai intai trebuie sa te autentifici.
Cod sursa(job #2948733)
Utilizator | Data | 28 noiembrie 2022 08:53:35 | |
---|---|---|---|
Problema | 1-sir | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 1.47 kb |
#include <fstream>
using namespace std;
ifstream cin("1-sir.in");
ofstream cout("1-sir.out");
const int NMAX = (1 << 8);
const int SMAX = 32896;
const int MOD = 194767;
int dp[2][2 * SMAX + 5], n, s;
int main(){
cin >> n >> s;
if(s < 0 && (n - 1) * n / 2 > s){
cout << 0;
return 0;
}
if((n - 1) * n / 2 < s){
cout << 0;
return 0;
}
dp[1][SMAX] = 1;
int curr = 0;
int ant = 1;
for(int i = 2; i <= n; i++){
int lim = i * (i - 1) / 2;
for(int j = -SMAX; j <= SMAX; j++)
dp[curr][j + SMAX] = 0;
for(int j = -lim; j <= lim; j++){
if(j + (i - 1) <= SMAX){
dp[curr][j + (i - 1) + SMAX] += dp[ant][j + SMAX];
dp[curr][j + (i - 1) + SMAX] %= MOD;
}
if(j - (i - 1) >= -SMAX){
dp[curr][j - (i - 1) + SMAX] += dp[ant][j + SMAX];
dp[curr][j - (i - 1) + SMAX] %= MOD;
}
}
/*
for(int j = -lim; j <= lim && i == n; j++){
if(dp[curr][j + SMAX]){
cout << "exista " << dp[curr][j + SMAX] << " siruri de lungime " << i << " si cu suma " << j << "\n";
}
}
cout << "\n\n";
*/
curr++;
ant++;
curr %= 2;
ant %= 2;
}
cout << dp[ant][s + SMAX];
return 0;
}