結果
問題 | No.1761 Sequence Distance |
ユーザー | 👑 ygussany |
提出日時 | 2021-11-20 16:34:58 |
言語 | C (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 5,810 ms / 8,000 ms |
コード長 | 1,010 bytes |
コンパイル時間 | 1,249 ms |
コンパイル使用メモリ | 41,684 KB |
実行使用メモリ | 9,748 KB |
最終ジャッジ日時 | 2023-09-02 11:45:34 |
合計ジャッジ時間 | 45,917 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
9,584 KB |
testcase_01 | AC | 4 ms
9,692 KB |
testcase_02 | AC | 994 ms
9,740 KB |
testcase_03 | AC | 3 ms
9,596 KB |
testcase_04 | AC | 4 ms
9,604 KB |
testcase_05 | AC | 4 ms
9,580 KB |
testcase_06 | AC | 5 ms
9,660 KB |
testcase_07 | AC | 3 ms
9,644 KB |
testcase_08 | AC | 6 ms
9,704 KB |
testcase_09 | AC | 5 ms
9,664 KB |
testcase_10 | AC | 6 ms
9,700 KB |
testcase_11 | AC | 7 ms
9,580 KB |
testcase_12 | AC | 5 ms
9,664 KB |
testcase_13 | AC | 4 ms
9,684 KB |
testcase_14 | AC | 4 ms
9,664 KB |
testcase_15 | AC | 6 ms
9,744 KB |
testcase_16 | AC | 8 ms
9,660 KB |
testcase_17 | AC | 4 ms
9,740 KB |
testcase_18 | AC | 7 ms
9,744 KB |
testcase_19 | AC | 5 ms
9,604 KB |
testcase_20 | AC | 4 ms
9,656 KB |
testcase_21 | AC | 635 ms
9,592 KB |
testcase_22 | AC | 28 ms
9,724 KB |
testcase_23 | AC | 4,256 ms
9,740 KB |
testcase_24 | AC | 997 ms
9,664 KB |
testcase_25 | AC | 3,245 ms
9,700 KB |
testcase_26 | AC | 3,690 ms
9,656 KB |
testcase_27 | AC | 824 ms
9,696 KB |
testcase_28 | AC | 783 ms
9,696 KB |
testcase_29 | AC | 2,915 ms
9,600 KB |
testcase_30 | AC | 303 ms
9,696 KB |
testcase_31 | AC | 1,417 ms
9,596 KB |
testcase_32 | AC | 46 ms
9,728 KB |
testcase_33 | AC | 1,638 ms
9,604 KB |
testcase_34 | AC | 5 ms
9,648 KB |
testcase_35 | AC | 70 ms
9,660 KB |
testcase_36 | AC | 2,404 ms
9,644 KB |
testcase_37 | AC | 160 ms
9,696 KB |
testcase_38 | AC | 372 ms
9,660 KB |
testcase_39 | AC | 1,192 ms
9,660 KB |
testcase_40 | AC | 249 ms
9,748 KB |
testcase_41 | AC | 4,779 ms
9,696 KB |
testcase_42 | AC | 5,803 ms
9,728 KB |
testcase_43 | AC | 5,810 ms
9,740 KB |
testcase_44 | AC | 4 ms
9,696 KB |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <stdio.h> const int Mod = 998244353; int main() { int N, M; scanf("%d %d", &N, &M); int i, j, k, cur, prev, dp[2][1003][1003] = {}; dp[0][0][0] = 2; for (i = 2, cur = 1, prev = 0; i <= N; i++, cur ^= 1, prev ^= 1) { for (j = (i - 1 < M)? i - 1: M; j > 0; j--) { for (k = 0; k <= M; k++) { if (j == M) dp[cur][j][k] = dp[prev][j-1][k]; else { dp[cur][j][k] = dp[cur][j+1][k] + dp[prev][j-1][k] - dp[prev][j][k]; if (dp[cur][j][k] >= Mod) dp[cur][j][k] -= Mod; else if (dp[cur][j][k] < 0) dp[cur][j][k] += Mod; } } for (k = j; k <= M; k++) { dp[cur][j][k] += dp[prev][j][k-j]; if (dp[cur][j][k] >= Mod) dp[cur][j][k] -= Mod; } if (j == i - 1) dp[cur][j][j]++; } for (k = 0; k <= M; k++) { dp[cur][0][k] = dp[cur][1][k] * 2; if (dp[cur][0][k] >= Mod) dp[cur][0][k] -= Mod; } } printf("%d\n", dp[prev][0][M]); fflush(stdout); return 0; }