提出 #25257535

ソースコード 拡げる

#include <cstddef>
#include <iostream>
#include <vector>

#include <atcoder/modint>

using usize = size_t;
using Modint = atcoder::modint998244353;

int main(void) {
  // input
  usize N, M;
  std::cin >> N >> M;

  // solve
  std::vector DP(2 * N + 1, std::vector(2 * M, Modint(0)));
  // DP[i][j] i 個の多角形を使っていて、j-M 個上段の方が多い場合の数
  // j=2*M は j=0 と重複するのでなし
  DP[0][M] = 1;

  for (usize i = 0; i < 2 * N; ++i) {
    std::vector<Modint> imos(2 * M + 10);
    for (usize j = 0; j < 2 * M; ++j) {
      if (j == M) {
        imos[0] += DP[i][j];
        imos[2 * M] -= DP[i][j];
      } else if (j == 0) {
        imos[M] += DP[i][j];
        imos[M + 2] -= DP[i][j];
      } else {
        const auto k = (j < M ? M - j : j - M);
        const auto l = M - k;
        if (j < M) {
          imos[M - l + 2] += DP[i][j];
          imos[M + l + 2] -= DP[i][j];
        } else {
          imos[M - l] += DP[i][j];
          imos[M + l] -= DP[i][j];
        }
      }
    }
    for (usize j = 2; j < 2 * M + 1; ++j)
      imos[j] += imos[j - 2];
    for (usize j = 0; j < 2 * M; ++j)
      DP[i + 1][j] = imos[j];
  }

  // output
  std::cout << DP[2 * N][M].val() << std::endl;
}

提出情報

提出日時
問題 L - Polyomino Tiling
ユーザ Cyanmond
言語 C++ (GCC 9.2.1)
得点 600
コード長 1291 Byte
結果 AC
実行時間 122 ms
メモリ 65948 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 600 / 600
結果
AC × 3
AC × 49
セット名 テストケース
Sample example0.txt, example1.txt, example2.txt
All almost_maximum0.txt, almost_maximum1.txt, almost_maximum2.txt, almost_maximum3.txt, almost_maximum4.txt, almost_maximum5.txt, almost_maximum6.txt, almost_maximum7.txt, almost_maximum8.txt, almost_maximum9.txt, example0.txt, example1.txt, example2.txt, hand0.txt, hand1.txt, hand2.txt, hand3.txt, hand4.txt, maximum0.txt, random0.txt, random1.txt, random10.txt, random11.txt, random12.txt, random13.txt, random14.txt, random15.txt, random16.txt, random17.txt, random18.txt, random19.txt, random2.txt, random20.txt, random21.txt, random22.txt, random23.txt, random24.txt, random25.txt, random26.txt, random27.txt, random28.txt, random29.txt, random3.txt, random4.txt, random5.txt, random6.txt, random7.txt, random8.txt, random9.txt
ケース名 結果 実行時間 メモリ
almost_maximum0.txt AC 118 ms 62856 KiB
almost_maximum1.txt AC 114 ms 61980 KiB
almost_maximum2.txt AC 111 ms 60408 KiB
almost_maximum3.txt AC 112 ms 62008 KiB
almost_maximum4.txt AC 116 ms 63016 KiB
almost_maximum5.txt AC 114 ms 60900 KiB
almost_maximum6.txt AC 111 ms 61344 KiB
almost_maximum7.txt AC 120 ms 64512 KiB
almost_maximum8.txt AC 115 ms 63204 KiB
almost_maximum9.txt AC 114 ms 62348 KiB
example0.txt AC 2 ms 3656 KiB
example1.txt AC 2 ms 3640 KiB
example2.txt AC 4 ms 3828 KiB
hand0.txt AC 2 ms 3504 KiB
hand1.txt AC 1 ms 3680 KiB
hand2.txt AC 3 ms 3728 KiB
hand3.txt AC 1 ms 3608 KiB
hand4.txt AC 4 ms 3772 KiB
maximum0.txt AC 122 ms 65948 KiB
random0.txt AC 21 ms 9720 KiB
random1.txt AC 69 ms 36668 KiB
random10.txt AC 68 ms 35208 KiB
random11.txt AC 30 ms 12828 KiB
random12.txt AC 37 ms 17596 KiB
random13.txt AC 33 ms 14380 KiB
random14.txt AC 52 ms 24760 KiB
random15.txt AC 9 ms 5396 KiB
random16.txt AC 71 ms 34192 KiB
random17.txt AC 30 ms 12660 KiB
random18.txt AC 15 ms 6432 KiB
random19.txt AC 75 ms 40064 KiB
random2.txt AC 76 ms 39432 KiB
random20.txt AC 18 ms 6164 KiB
random21.txt AC 46 ms 22148 KiB
random22.txt AC 11 ms 5232 KiB
random23.txt AC 102 ms 52056 KiB
random24.txt AC 45 ms 20596 KiB
random25.txt AC 83 ms 43184 KiB
random26.txt AC 36 ms 16556 KiB
random27.txt AC 17 ms 9128 KiB
random28.txt AC 38 ms 14472 KiB
random29.txt AC 6 ms 3992 KiB
random3.txt AC 29 ms 15820 KiB
random4.txt AC 33 ms 15840 KiB
random5.txt AC 57 ms 30196 KiB
random6.txt AC 79 ms 42020 KiB
random7.txt AC 102 ms 54916 KiB
random8.txt AC 47 ms 21776 KiB
random9.txt AC 21 ms 9184 KiB