Cod sursa(job #2802053)

Utilizator vansJos da pa perete vans Data 17 noiembrie 2021 13:55:00
Problema 1-sir Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 256, MOD = 194767;

int n, s, dp[2][NMAX + 1];

inline int vabs(const int X) {
    return X > 0 ? X : -X;
}

int main()
{
    freopen("1-sir.in", "r", stdin);
    freopen("1-sir.out", "w", stdout);
    scanf("%d%d", &n, &s);

    const int valmax = n * (n - 1) / 2;
    s = vabs(s);
    if(s > valmax) {
        printf("0");
        return 0;
    }
    dp[0][0] = 1;
    int ind = 1;
    for(int i = 1; i < n; ++i, ind ^= 1) {
        for(int suma = 0; suma <= i * (i + 1) / 2; ++suma) {
            dp[ind][suma] = (1ll * dp[ind ^ 1][vabs(suma - i)] + dp[ind ^ 1][vabs(suma + i)]) % MOD;
        }
    }
    printf("%d", dp[ind ^ 1][s]);
    return 0;
}