Cod sursa(job #2019134)

Utilizator vladdy47Bucur Vlad Andrei vladdy47 Data 7 septembrie 2017 09:38:47
Problema 1-sir Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
# include <bits/stdc++.h>
# define MOD 194767

using namespace std;

const int Nmax = 256, M = 1e4 * 7;

int n, S, Left, Right, i, j, dp[Nmax][M];

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

    scanf("%d %d\n", &n, &S);

    Left = (-1) * n * (n - 1) / 2;
    Right = n * (n - 1) / 2;

    int UP = Right + 1;

    if (S < Left || S > Right)
    {
        printf("0\n");
        return 0;
    }

    dp[0][UP] = 1;

    for (i = 1; i <= n; ++i)
    {
        if (i != 1)
        for (int k = Left; k <= Right; ++k)
            dp[0][k + UP] = dp[1][k + UP];

        for (j = Left; j <= Right; ++j)
        {
            dp[1][j + UP] = dp[0][j - i + UP] + dp[0][j + i + UP];
            if (dp[1][j + UP] >= MOD) dp[1][j + UP] -= MOD;
        }
    }


    printf("%d\n", dp[0][S + UP]);

    return 0;
}