Cod sursa(job #2021548)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 13 septembrie 2017 22:15:46
Problema 1-sir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <cstdio>

using namespace std;

const int nmax = 256;
const int mod = 194767;

int dp[2][nmax*nmax + 1];

int modul(int a) {
    if(a > 0)
        return a;
    return -a;
}

int main() {
    freopen("1-sir.in", "r", stdin);
    freopen("1-sir.out", "w", stdout);

    int n, s, maxim;
    scanf("%d%d", &n, &s);

    maxim = n * (n + 1) / 2;

    if(s > maxim || s < -maxim) {
        printf("0\n");
        return 0;
    }

    int l = 1;

    dp[0][0] = 1;
    for(int i = 2; i <= n; ++ i, l = 1 - l) {
        for(int j = 0; j <= maxim; ++ j) {
            dp[l][j] = (dp[1 - l][modul(j - (i - 1))] + dp[1 - l][modul(j + (i - 1))]) % mod;
        }
    }

    printf("%d\n", dp[1 - l][s]);

    return 0;
}