Cod sursa(job #3144792)

Utilizator Traian_7109Traian Mihai Danciu Traian_7109 Data 10 august 2023 18:06:16
Problema 1-sir Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 256, mod = 194767;
int dp1[NMAX * NMAX], dp2[NMAX * NMAX];

int main() {
    #ifndef TEST 
        freopen("1-sir.in", "r", stdin);
        freopen("1-sir.out", "w", stdout);
    #endif
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    
    int n, sum;
    cin >> n >> sum;
    sum = abs(sum);
    if (sum > n * (n - 1) / 2) {
        cout << "0";
        return 0;
    }
    dp1[0] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= i * (i + 1) / 2; j++)
            dp2[j] = (dp1[abs(i + j - 1)] + dp1[abs(i - j - 1)]) % mod;
        for (int j = 0; j <= i * (i + 1) / 2; j++)
            dp1[j] = dp2[j];
    }
    cout << dp1[sum];
    return 0;
}