Cod sursa(job #2579583)

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

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

const int r = 194767;
int dp[2][2*32640+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] = 0;
        for (j = -smax+e; j<=smax; j++)
            dp[l][smax+j] = dp[1-l][smax+j-e];
        for (j = -smax; j<=smax-e; j++)
            dp[l][smax+j] = (dp[l][smax+j] + dp[1-l][smax+j+e])%r;
    }
    fout << dp[1-l][smax+s];
    return 0;
}