Cod sursa(job #2940070)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 14 noiembrie 2022 19:18:55
Problema 1-sir Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
using ll = long long;

using namespace std;

const int NMAX = 256;
const int SMAX = NMAX * (NMAX - 1) / 2;
const int MOD = 194767;
/*******************************/
// INPUT / OUTPUT

ifstream f("1-sir.in");
ofstream g("1-sir.out");
/*******************************/
/// GLOBAL DECLARATIONS

int N, S;
int ans;
int aux[2][2 * SMAX + 1], *nr[2];
/*******************************/
/// FUNCTIONS

void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
    f >> N >> S;
}
///-------------------------------------
inline void Solution()
{
    if (S > N * (N - 1) / 2 || S < -N * (N - 1) / 2)
    {
        return;
    }
    nr[0] = aux[0] + SMAX;
    nr[1] = aux[1] + SMAX;
    nr[1][0] = 1;
    for (int i = 2; 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, sizeof(aux[i_c]));
        ///obiectul i
        for (int j = lim - (i - 1); j >= -lim; j--)
        {
            nr[i_c][j + (i - 1)] = nr[i_a][j];
        }
        ///obiectul -i
        for (int j = -lim + (i - 1); j <= lim; j++)
        {
            nr[i_c][j - (i - 1)] += nr[i_a][j];
            nr[i_c][j - (i - 1)] %= MOD;
        }
    }
    ans = nr[N % 2][S];
}
///-------------------------------------
inline void Output()
{
    g << ans;
}
///-------------------------------------
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ReadInput();
    Solution();
    Output();
    return 0;
}