Cod sursa(job #2579586)

Utilizator popoviciAna16Popovici Ana popoviciAna16 Data 12 martie 2020 17:10:16
Problema 1-sir Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <fstream>
using namespace std;

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

const int r = 194767;
int dp[2][2*33000+1];

int main()
{
    int i, n, j, s, smax, l, e;
    fin >> n >> s;
    if (s < 0)
        s = -s;
    if (s > n*(n-1)/2)
    {
        fout << 0;
        return 0;
    }
    l = 0;
    smax = n*(n-1)/2;
    dp[1][smax+n-1] = 1;
    dp[1][smax-n+1] = 1;
    for (i = 3; i<=n; i++, l = 1-l)
    {
        e = n-i+1;
        for (j = -smax; j<=smax; j++)
            dp[l][smax+j] = (dp[1-l][smax+j-e] + dp[1-l][smax+j+e])%r;
    }
    fout << dp[1-l][smax+s];
    return 0;
}