Cod sursa(job #2139388)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 22 februarie 2018 14:59:10
Problema 1-sir Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <cstdio>
using namespace std;

#define MOD 194767

int N, S;
int dp[2][256 * 256];
int smax;

int absx(int x) {
  return x < 0 ? -x : x;
}

void dinamica() {
  dp[0][0] = 1;
  int line = 1;

  for (int i = 2; i <= N; i++) {
    for (int j = 0; j <= smax; j++) {
      dp[line][j] = (dp[line ^ 1][absx(j - i + 1)] + dp[line ^ 1][absx(j + i - 1)]) % MOD;
      printf("%d ", dp[line][j]);
    }
    line ^= 1;
  }

  printf("%d", dp[line ^ 1][S]);
}

int main() {
  freopen("1-sir.in", "r", stdin);
  freopen("1-sir.out", "w", stdout);
  scanf("%d %d ", &N, &S);
  smax = N * (N + 1) / 2;
  if (S > smax || S < -smax) {
    printf("0");
    return 0;
  }
  dinamica();
  return 0;
}