結果

問題 No.3213 depth max K
コンテスト
ユーザー Cafe1942
提出日時 2025-06-13 20:40:20
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 668 ms / 2,000 ms
コード長 754 bytes
コンパイル時間 755 ms
コンパイル使用メモリ 69,128 KB
実行使用メモリ 395,008 KB
最終ジャッジ日時 2025-06-13 20:47:43
合計ジャッジ時間 20,378 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
using ll = long long;
using namespace std;

int main() {
	int N, K;
	cin >> N >> K;
	ll dpUpper[5005][5005] = { 0 };
	ll dpLower[5005][5005] = { 0 };
	for (int i = 0;i <= K;i++) {
		dpUpper[i][0] = 1;
	}
	for (int j = 1;j <= N;j++) {
		dpUpper[j][j] = dpUpper[j][j - 1];
		for (int i = j + 1;i - j <= K && i <= N;i++) {
			dpUpper[i][j] = (dpUpper[i][j - 1] + dpUpper[i - 1][j]) % 998244353;
		}
	}
	for (int i = 0;i <= K - 1;i++) {
		dpLower[i][0] = 1;
	}
	for (int j = 1;j <= N;j++) {
		dpLower[j][j] = dpLower[j][j - 1];
		for (int i = j + 1;i - j <= K - 1 && i <= N;i++) {
			dpLower[i][j] = (dpLower[i][j - 1] + dpLower[i - 1][j]) % 998244353;
		}
	}
	cout << (dpUpper[N][N] - dpLower[N][N] + 998244353) % 998244353;
	return 0;
}
0