Cod sursa(job #1988766)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 4 iunie 2017 17:43:02
Problema 1-sir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

const int nMax = 260;
const int sMax = (nMax * (nMax - 1)) / 2;
const int MOD = 194767;

int n, s;
int dp[2][sMax];

void citire()
{
    ifstream in("1-sir.in");
    in >> n >> s;
    in.close();
}

void rezolvare()
{
    ofstream out("1-sir.out");
    s = abs(s);
    if(s > n * (n-1) / 2)
    {
        out << 0;
        return;
    }
    s = n * (n - 1) / 2 - s;
    if(s % 2 != 0)
    {
        out << 0;
        return;
    }
    s /= 2;
    --n;
    int current = 0, last = 1;
    dp[current][1] = dp[current][0] = 1;
    for(int i = 2; i <= n; ++i)
    {
        swap(current, last);
        for(int j = 0; j <= s; ++j)
        {
            dp[current][j] = dp[last][j];
            if(j - i >= 0)
                dp[current][j] = (dp[current][j] + dp[last][j-i]) % MOD;
        }
    }
    out << dp[current][s];
}

int main()
{
    citire();
    rezolvare();
    return 0;
}