Cod sursa(job #2515694)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 29 decembrie 2019 12:03:32
Problema 1-sir Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>

using namespace std;

ifstream fin("1-sir.in");
ofstream fout("1-sir.out");

const int MOD = 194767;

const int NMAX = 256;
const int SMAX = NMAX * NMAX / 2;

int N, S;

inline int ABS(int x)
{
    return max(x, -x);
}

int dp[2][SMAX + 5];

int main()
{
    fin >> N >> S;

    if((N - 1) * N / 2 < ABS(S))
    {
        fout << 0 << '\n';
        return 0;
    }

    dp[1][0] = 1;

    for(int i = 2; i <= N; i++)
    {
        int line = (i & 1);
        int prevLine = 1 - line;

        for(int j = 0; j <= (i - 1) * i / 2; j++)
        {
            int sL = ABS(j - (i - 1));
            int sR = ABS(j + (i - 1));

            dp[line][j] = (dp[prevLine][sL] + dp[prevLine][sR]) % MOD;
        }
    }

    fout << dp[N & 1][S] << '\n';

    return 0;
}