Cod sursa(job #2035546)

Utilizator lflorin29Florin Laiu lflorin29 Data 9 octombrie 2017 16:59:17
Problema 1-sir Scor 70
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][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[l][idx(full)] = 1;

    for(int i = 2; i <= n; ++ i) {
        memset(dp[l ^ 1], 0, sizeof dp[l ^ 1]);
        l ^= 1;
        int decr = 2 * (n - i + 1);
        for(int j = -full; j <= full; ++ j) {
          dp[l][idx(j)] = dp[l ^ 1][idx(j)];
          dp[l ][idx(j)] += dp[l ^ 1][idx(j + decr)];
          if(dp[l][idx(j)] >= mod)
            dp[l][idx(j)] -= mod;
        }
    }
    cout << dp[l][idx(s)];
}