Cod sursa(job #1718465)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 17 iunie 2016 22:28:37
Problema 1-sir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
#include <cstring>

using namespace std;

const int MOD = 194767;
const int NMAX = 256;

int dp[2][NMAX * NMAX];

void add(int &where, int val) {
    where += val;
    if (where >= MOD)
        where -= MOD;
}

int main()
{
    ifstream cin("1-sir.in");
    ofstream cout("1-sir.out");

    int n = 0, s;
    cin >> n >> s;
    if (s < 0)
        s = -s;

    int trans = n * (n - 1) / 2;
    if (s > trans) {
        cout << "0\n";
        return 0;
    }

    dp[1][trans] = 1;
    for (int i = 1; i < n; ++ i) {
        memset(dp[(i & 1) ^ 1], 0, sizeof dp[(i & 1) ^ 1]);

        int aux = i * (i - 1) / 2;
        for (int j = trans - aux; j <= trans + aux; ++ j)
            if (dp[i & 1][j]) {
                add(dp[(i & 1) ^ 1][j + i], dp[i & 1][j]);
                add(dp[(i & 1) ^ 1][j - i], dp[i & 1][j]);
            }
    }

    cout << dp[n & 1][s + trans] << '\n';

    cin.close();
    cout.close();
    return 0;
}