Cod sursa(job #2999835)

Utilizator tomaionutIDorando tomaionut Data 11 martie 2023 16:29:07
Problema 1-sir Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <bits/stdc++.h>
#define MOD 194767
using namespace std;

ifstream fin("1-sir.in");
ofstream fout("1-sir.out");
int n, s, dp[300][33000];
int main()
{
    int i, n, s, j, curr;
    fin >> n >> s;
    if (n * (n - 1) / 2 < s or -1 * (n * (n - 1) / 2) > s)
    {
        fout << "0\n";
        return 0;
    }

    dp[1][0] = 1;
    curr = 0;
    for (i = 2; i <= n; i++, curr ^= 1)
    {
        for (j = 0; j < i; j++)
            dp[curr][j] = (dp[curr ^ 1][i - j - 1] + dp[curr ^ 1][i + j - 1]) % MOD;
        for (j = i; j <= (i * (i - 1) / 2); j++)
            dp[curr][j] = (dp[curr ^ 1][j - i + 1] + dp[curr ^ 1][j + i - 1]) % MOD;
    }
    fout << dp[curr ^ 1][s];

    return 0;
}