Cod sursa(job #2300426)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 11 decembrie 2018 12:48:13
Problema 1-sir Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;

ifstream f ("1-sir.in");
ofstream g ("1-sir.out");

const int NMAX = 260;
const int MOD = 194767;

int n, s;
int dp[2][NMAX * NMAX / 2];

void add (int &a, int b) {
    a = (a + b) % MOD;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef LOCAL_DEFINE
    freopen (".in", "r", stdin);
#endif

    f >> n >> s;
    s = abs (s);
    if (s > n * (n - 1) / 2) {
        g << "0\n";
        return 0;
    }

    int now = 1, old = 0;
    dp[old][0] = 1;
    for (int i = 2; i <= n; ++i) {
        for (int j = 0; j <= i * (i - 1) / 2; ++j) {
            dp[now][j] = 0; // dupa o mancarica buna m am prins :)
            add (dp[now][j], dp[old][abs (j - (i - 1))]);
            add (dp[now][j], dp[old][abs (j + (i - 1))]);
        }
        swap (old, now);
    }

    g << dp[old][s] << '\n';

    f.close();
    g.close();
    return 0;
}