Cod sursa(job #844184)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 28 decembrie 2012 21:45:53
Problema 1-sir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <cstdio>
#include <cassert>

using namespace std;

const int Mod = 194767;
const int MaxSum = 70000;

int N, Sum, DP[MaxSum], Solution;

void Solve() {
    Solution = 0;
    int MaxS = N * (N - 1) / 2;
    if (Sum < -MaxS || Sum > MaxS)
        return;
    DP[0] = 1, MaxS = 0;
    for (int i = 2; i <= N; ++i) {
        int Value = 2 * (N - i + 1);
        for (int s = MaxS; s >= 0; --s)
            DP[s + Value] = (DP[s + Value] + DP[s]) % Mod;
        MaxS += Value;
    }
    Solution = DP[N * (N - 1) / 2 - Sum];
}

void Read() {
    assert(freopen("1-sir.in", "r", stdin));
    assert(scanf("%d %d", &N, &Sum));
}

void Print() {
    assert(freopen("1-sir.out", "w", stdout));
    printf("%d\n", Solution);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}