結果
問題 | No.3052 Increasing Sliding Window Minimum |
ユーザー |
![]() |
提出日時 | 2025-03-07 21:56:13 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 99 ms / 2,000 ms |
コード長 | 1,012 bytes |
コンパイル時間 | 4,459 ms |
コンパイル使用メモリ | 253,200 KB |
実行使用メモリ | 8,608 KB |
最終ジャッジ日時 | 2025-03-07 21:56:28 |
合計ジャッジ時間 | 6,621 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 42 |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000000 #define Inf64 1000000000000000001LL int main(){ int _t; cin>>_t; rep(_,_t){ int n; cin>>n; vector<int> pos(n,-1); vector<int> aa(n); rep(i,n){ int a; cin>>a; a--; aa[i] = a; if(a>=0)pos[a] = i+1; } vector<mint> dp(n+1,0); dp[0] = 1; rep(i,n){ vector<mint> ndp(n+1,0); mint booked = 0; rep(j,n+1){ if(j>0 && aa[j-1]>i)booked++; if(dp[j]==0)continue; if(pos[i]==-1){ { ndp[j] += dp[j] * (j-i-booked); } for(int k=1;k<=2;k++){ if(j+k <= n && aa[j+k-1]==-2)ndp[j+k] += dp[j]; } } else{ if(pos[i] - j <= 2){ ndp[max(pos[i],j)] += dp[j]; } } } swap(dp,ndp); /*rep(j,n+1){ cout<<dp[j].val()<<' '; } cout<<endl;*/ } cout<<dp[n].val()<<endl; } return 0; }