Cod sursa(job #2019140)

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

using namespace std;

const int Nmax = 256, M = Nmax * Nmax + 5;

int n, S, Left, Right, i, j, dp[2][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)
    {
        int lim_left = (-1) * i * (i + 1) / 2, lim_right = i * (i + 1) / 2;

        if (i != 1)
        for (int k = lim_left; k <= lim_right; ++k)
            dp[0][k + UP] = dp[1][k + UP];

        for (j = lim_left; j <= lim_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[1][S + UP]);

    return 0;
}