Cod sursa(job #2940069)

Utilizator rapidu36Victor Manz rapidu36 Data 14 noiembrie 2022 19:17:46
Problema 1-sir Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <cstring>

using namespace std;

const int N = 256;
const int MOD = 194767;

int aux[2][N*(N-1)+1], *nr[2];

int main()
{
    ifstream in("1-sir.in");
    ofstream out("1-sir.out");
    int n, s;
    in >> n >> s;
    if (s < 0)
    {
        s = -s;
    }
    in.close();
    if (s > n * (n - 1) / 2)
    {
        out << 0;
        out.close();
        return 0;
    }
    nr[0] = aux[0] + N * (N - 1) / 2;
    nr[1] = aux[1] + N * (N - 1) / 2;
    nr[0][0] = 1;
    for (int i = 1; i < n; i++)
    {
        ///actualizez cu obiecte de greutati i si -i
        int i_c = i % 2;
        int i_a = 1 - i_c;
        int lim = i * (i + 1) / 2;
        memset(aux[i_c], 0, (N*(N-1) + 1) * sizeof(int));
        ///obiectul i
        for (int j = lim - i; j >= -lim; j--)
        {
            nr[i_c][j + i] = nr[i_a][j];
        }
        ///obiectul -i
        for (int j = -lim + i; j <= lim; j++)
        {
            nr[i_c][j - i] += nr[i_a][j];
            nr[i_c][j - i] %= MOD;
        }
        /*
        for (int j = -s; j <= s; j++)
        {
            out << nr[i_c][j] << " ";
        }
        out << "\n";
        */
    }
    out << nr[1 - n % 2][s];
    out.close();
    return 0;
}