Cod sursa(job #2579609)

Utilizator popoviciAna16Popovici Ana popoviciAna16 Data 12 martie 2020 17:34:07
Problema 1-sir Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
using namespace std;
 
ifstream fin("1-sir.in");
ofstream fout("1-sir.out");
 
const int r = 194767;
int v1[2*33001], v2[2*33001];
int *dp1, *dp2;
 
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;
    dp1 = v1+33001;
    dp2 = v2+33001;
    dp2[n-1] = dp2[-n+1] = 1;
    for (i = 3; i<=n; i++, l = 1-l)
    {
        e = n-i+1;
        if (i%2)
            for (j = -smax; j<=smax; j++)
                dp1[j] = (dp2[j-e] + dp2[j+e])%r;
        else
            for (j = -smax; j<=smax; j++)
                dp2[j] = (dp1[j-e] + dp1[j+e])%r;
    }
    if (n%2)
        fout << dp1[s];
    else
        fout << dp2[s];
    return 0;
}