Cod sursa(job #1410252)

Utilizator Ionut228Ionut Calofir Ionut228 Data 30 martie 2015 22:54:40
Problema 1-sir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#include <cstdlib>

using namespace std;

ifstream fin("1-sir.in");
ofstream fout("1-sir.out");

const int MOD = 194767;

int N, S, sum;
int dp[259][(259 * 258) / 2];

int main()
{
    fin >> N >> S;
    dp[0][0] = 1;
    int l = 1;
    sum = 0;
    for (int i = 2; i <= N; ++i, l = 1 - l)
    {
        sum += i - 1;
        int j = 0;
        int lt = abs(j - (i - 1));
        int rt = j + (i - 1);
        while (j < i - 1 && j <= sum)
        {
            dp[l][j] = (dp[1 - l][lt] + dp[1 - l][rt]) % MOD;
            ++j;
            lt = abs(j - (i - 1));
            rt = j + (i - 1);
        }
        lt = 0;
        rt = 2 * j;
        for (; j <= sum; ++j)
        {
            dp[l][j] = (dp[1 - l][lt] + dp[1 - l][rt]) % MOD;
            ++lt;
            ++rt;
        }
    }

    l = 1 - l;
    fout << dp[l][int(abs(S))] << '\n';

    fin.close();
    fout.close();
    return 0;
}