Cod sursa(job #2035555)

Utilizator lflorin29Florin Laiu lflorin29 Data 9 octombrie 2017 17:03:37
Problema 1-sir Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <bits/stdc++.h>

using namespace std;

const int N = 256, mod = 194767;

int l, n, s, dp[2 * N * N];

int idx(int pos) {
    return pos + N * N;
}
int main() {
    freopen("1-sir.in", "r", stdin);
    freopen("1-sir.out", "w", stdout);

    cin >> n >> s;

    int full = (n - 1) * n / 2;

    if(abs(s) > full) {
        cout << 0;
        return 0;
    }

    l = 0;
    dp[idx(full)] = 1;
    int totDecr = 0;

    for(int i = 2; i <= n; ++ i) {
        int decr = 2 * (n - i + 1);
        for(int j = full-totDecr; j <= full; ++ j) {
            if(j + decr <= full ) {
                dp[idx(j)] += dp[idx(j + decr)];

                if(dp[idx(j)] >= mod)
                    dp[idx(j)] -= mod;
            }
        }

        totDecr += decr;
    }

    cout << dp[idx(s)];
}