結果

問題 No.3096 Snake Path
ユーザー 👑 ygussany
提出日時 2025-03-09 15:41:34
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 10 ms / 2,000 ms
コード長 1,537 bytes
コンパイル時間 355 ms
コンパイル使用メモリ 27,392 KB
実行使用メモリ 8,612 KB
最終ジャッジ日時 2025-03-09 15:41:36
合計ジャッジ時間 1,986 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 35
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:8:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    8 |         scanf("%d %d", &N ,&K);
      |         ^~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #

#include <stdio.h>

const int Mod = 998244353;

int main()
{
	int N, K;
	scanf("%d %d", &N ,&K);
	if (N == 1) {
		printf("1\n");
		return 0;
	}
	
	int i, j, k, cur, prev;
	long long dp[2][5][2005] = {}, tmp[5];
	for (i = 1, cur = 1, prev = 0, dp[0][0][0] = 1; i <= N; i++, cur ^= 1, prev ^= 1) {
		for (k = 0; k <= K && k <= (i - 1) * 2; k++) {
			for (j = 0; j < 5; j++) {
				tmp[j] = dp[prev][j][k] % Mod;
				dp[prev][j][k] = 0;
			}
			if (i % 2 == 0) {
				dp[cur][0][k+1] += tmp[0];
				dp[cur][1][k+1] += tmp[0];
				dp[cur][2][k+1] += tmp[0];
				dp[cur][3][k+1] += tmp[0];
				dp[cur][0][k+1] += tmp[1];
				dp[cur][1][k+1] += tmp[1];
				dp[cur][2][k+1] += tmp[1];
				dp[cur][0][k] += tmp[2];
				dp[cur][1][k] += tmp[2];
				dp[cur][2][k] += tmp[2];
				dp[cur][4][k] += tmp[2];
				dp[cur][2][k+2] += tmp[3];
				dp[cur][3][k+2] += tmp[3];
				dp[cur][0][k+2] += tmp[4];
				dp[cur][4][k+2] += tmp[4];
			} else {
				dp[cur][0][k] += tmp[0];
				dp[cur][1][k] += tmp[0];
				dp[cur][2][k] += tmp[0];
				dp[cur][3][k] += tmp[0];
				dp[cur][0][k+1] += tmp[1];
				dp[cur][1][k+1] += tmp[1];
				dp[cur][2][k+1] += tmp[1];
				dp[cur][0][k+1] += tmp[2];
				dp[cur][1][k+1] += tmp[2];
				dp[cur][2][k+1] += tmp[2];
				dp[cur][4][k+1] += tmp[2];
				dp[cur][2][k+2] += tmp[3];
				dp[cur][3][k+2] += tmp[3];
				dp[cur][0][k+2] += tmp[4];
				dp[cur][4][k+2] += tmp[4];
			}
		}
	}
	
	long long ans = 0;
	for (k = 0; k <= K; k++) ans += dp[prev][N%2*2][k] % Mod;
	printf("%lld\n", ans % Mod);
	fflush(stdout);
	return 0;
}
0