Cod sursa(job #2823786)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 29 decembrie 2021 18:27:50
Problema 1-sir Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;

inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}

const int MOD = 194767;

int dp[2][1 << 17];
int N, S, sum;

int add_(int a, int b) {
    a += b;
    while(a >= MOD)
        a -= MOD;
    return a;
}

void solve() {
    cin >> N >> S;
    S = abs(S);

    sum = (N * (N - 1)) / 2;
    if(S > sum) {
        cout << 0;
        return;
    }

    dp[1][0] = 1;
    for(int i = 1, idx = 0;i < N;i++, idx ^= 1)  {
        for(int sum = 0;sum <= (i * (i + 1) / 2);sum++)
            dp[idx][sum] = add_(dp[idx ^ 1][sum + i], dp[idx ^ 1][abs(sum - i)]);
    }

    cout << dp[N & 1][S];

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    Open("1-sir");

    int T = 1;
    for(;T;T--) {
        solve();
    }

    return 0;
}