結果
問題 | No.1378 Flattening |
ユーザー |
![]() |
提出日時 | 2020-10-14 19:40:28 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 638 bytes |
コンパイル時間 | 1,762 ms |
コンパイル使用メモリ | 58,972 KB |
実行使用メモリ | 199,040 KB |
最終ジャッジ日時 | 2024-07-20 19:22:25 |
合計ジャッジ時間 | 8,449 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 1 |
other | AC * 29 WA * 21 |
ソースコード
#include <iostream> #include <cassert> #include <algorithm> #define llint long long #define mod 998244353 using namespace std; llint n; llint a[5005], b[5005]; llint dp[5005][5005]; int main(void) { cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; assert(n >= 1 && n <= 5000); for(int i = 1; i <= n; i++) b[i] = a[i]; sort(b+1, b+n+1); for(int i = 1; i <= n; i++) assert(b[i] == i); dp[0][1] = 1; for(int i = 0; i <= n; i++){ for(int j = 1; j <= n; j++){ if(i+1 <= n && a[i+1] >= a[j]) (dp[i+1][j] += dp[i][j]) %= mod; if(j+1 <= n) (dp[i][j+1] += dp[i][j]) %= mod; } } cout << dp[n][n] << endl; return 0; }