Cod sursa(job #2035557)

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

using namespace std;

const int N = 256, mod = 194767;

int l, n, s, dp[2 * N * N], rest[2 * mod];
#define idx(pos) ((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;
    }

    for(int i = 0; i < mod; ++i) rest[i] = i;
    for(int i = mod; i < 2 * mod; ++ i) rest[i] = i - mod;

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

    for(int i = 2; i <= n; ++ i) {
        int decr = 2 * (n - i + 1);

        for(int j = -full; j <= full - decr; ++ j) {
            dp[idx(j)] = rest [ dp[idx(j)] + dp[idx(j + decr)] ];

        }
    }

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