Cod sursa(job #2935968)

Utilizator davidenko22Stancu David-Andrei davidenko22 Data 7 noiembrie 2022 19:16:29
Problema 1-sir Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MOD = 194767;

int dp[2][66000];

int main()
{
    int n, s = 0, maxi;
    fin >> n >> s;
    maxi = n * ( n + 1 ) / 2;
    dp[0][0] = 1;
    if ( s > maxi )
      fout << 0;
    else {
      for ( int i = 1; i < n; i++ ) {
        for ( int sum = 0; sum <= ( i * ( i + 1 ) ) / 2; sum++ ) {
          dp[1][sum] = dp[0][sum + i] + dp[0][max(sum - i, -sum + i)];
          dp[1][sum] = dp[1][sum] % MOD;

        }
        for ( int j = 0; j <= ( i * (i + 1) ) / 2; j++ ) {
          dp[0][j] = dp[1][j];
          dp[1][j] = 0;
        }
      }
      fout << dp[0][max(s, -s)];
    }
    return 0;
}