Cod sursa(job #2948723)

Utilizator Theodor17Pirnog Theodor Ioan Theodor17 Data 28 noiembrie 2022 08:07:44
Problema 1-sir Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 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)
        s = -s;

    if(s > (n - 1) * n / 2){

        cout << 0;
        return 0;

    }

    dp[1][SMAX] = 1;

    int curr = 0;
    int ant = 1;
    for(int i = 2; i <= n; i++){

        for(int j = -SMAX; j <= SMAX; 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 = -SMAX; j <= SMAX; 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;
}