Cod sursa(job #2716866)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 5 martie 2021 20:15:25
Problema 1-sir Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <bits/stdc++.h>
#define ABS(x) ((x) >= 0 ? (x) : -(x))

using namespace std;

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

const int mod = 194767;
const int NMAX = 1 << 8;
const int SMAX = 1 << 16;
int N, S, dp[2][SMAX], ind;

int main() {
    fin >> N >> S;
    const int max_sum = (N * (N - 1)) >> 1;
    if(ABS(S) > max_sum) {
        fout << "0\n";
        return 0;
    }
    dp[1][0] = 1;
    for(int i = 2; i <= N; ++i, ind ^= 1)
        for(int sum = 0; sum <= ((i - 1) * i) >> 1; ++sum)
            dp[ind][sum] = (dp[ind ^ 1][ABS(sum - (i - 1))] + dp[ind ^ 1][ABS(sum + (i - 1))]) % mod;
    fout << dp[ind ^ 1][ABS(S)] << '\n';
}