Cod sursa(job #3291163)

Utilizator Manolea_Teodor_StefanManolea Teodor Stefan Manolea_Teodor_Stefan Data 3 aprilie 2025 13:24:35
Problema 1-sir Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

//#define fin cin
//#define fout cout

using namespace std;
ifstream fin("1-sir.in");
ofstream fout("1-sir.out");
using ll = long long;


const int mod = 194767;

int n,s;
int prv, cur = 1;
array<unordered_map<ll,unordered_map<ll,ll>>,2> dp;
int main() {
    fin >> n >> s;
    dp[prv][0][0]++;
    for (int i = 1; i < n; i++) {
        dp[cur].clear();
        for (auto [idx,mp] : dp[prv]) {
            for (auto [bfr,cnt] : mp) {
                if (idx + bfr - 1 <= s) {
                    dp[cur][idx + bfr - 1][bfr - 1] += cnt;
                    dp[cur][idx + bfr - 1][bfr - 1] %= mod;
                }
                if (idx + bfr + 1 <= s) {
                    dp[cur][idx + bfr + 1][bfr + 1] += cnt;
                    dp[cur][idx + bfr + 1][bfr + 1] %= mod;
                }
            }
        }
        prv = !prv;
        cur = !cur;
    }
    ll ans = 0;
    for (auto [dontCare,cnt] : dp[prv][s]) {
        ans += cnt;
        ans %= mod;
    }
    fout << ans;
    return 0;
}