Cod sursa(job #2855741)

Utilizator Stefan_DomuncoStefan Domunco Stefan_Domunco Data 22 februarie 2022 20:49:25
Problema 1-sir Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
// Obs: O suma cu i elemente o construiesc in functie de primul semn
// primul semn il adaug la solutiile anterioare, iar acesta imi afecteaza solutia cu i-1 (+ sau -, in functie de semnul ales)
// de aici iese recurenta
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 300, MOD = 194767;
int dp[2][NMAX * NMAX]; // dp[i][j] - cate sume de i elemente am, suma si suma j

inline void swapLines()
{
    int i;
    for(i = 0; i < NMAX * NMAX; ++i)
        dp[0][i] = dp[1][i];
}

int main()
{
    int n, s;
    fin >> n >> s;
    s = abs(s);

    if(s > n * (n + 1) / 2)
    {
        fout << "0";
        return 0;
    }

    int lcurent, sumMax = n * (n + 1) / 2, sumCurrent;
    dp[1][0] = 1;

    for(lcurent = 2; lcurent <= n; ++lcurent)
    {
        swapLines();
        for(sumCurrent = 0; sumCurrent <= sumMax; ++sumCurrent)
        {
            dp[1][sumCurrent] = dp[0][sumCurrent + lcurent - 1] + dp[0][abs(sumCurrent - lcurent + 1)];

            if(dp[1][sumCurrent] >= MOD)
                dp[1][sumCurrent] -= MOD;
        }
    }

    fout << dp[1][s];

    return 0;
}