結果
問題 | No.1378 Flattening |
ユーザー |
|
提出日時 | 2024-04-01 18:11:56 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 367 ms / 2,000 ms |
コード長 | 1,363 bytes |
コンパイル時間 | 2,439 ms |
コンパイル使用メモリ | 213,136 KB |
実行使用メモリ | 199,168 KB |
最終ジャッジ日時 | 2024-09-30 21:56:30 |
合計ジャッジ時間 | 8,103 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 50 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/modint>#include <atcoder/segtree>using namespace atcoder;using namespace std;using ll = long long;using mint = modint998244353;int op(int a, int b) {return min(a,b);}int inf = 1e9;int e() {return inf;}int main() {int N;cin >> N;vector<int> A(N + 1, 0);for (int i = 1;i <= N;i++) cin >> A[i];vector<vector<mint>> dp(N + 1, vector<mint>(N + 1, 0));segtree<int, op, e> seg(A);vector<int> L(N + 1), R(N + 1);for (int j = 1;j <= N;j++) {int ok = j;int ng = 0;while (ok - ng > 1) {int x = (ok + ng) / 2;if (seg.prod(x, j + 1) == A[j]) {ok = x;} else {ng = x;}}int l = ok;ok = j;ng = N + 1;while (ng - ok > 1) {int x = (ok + ng) / 2;if (seg.prod(j, x + 1) == A[j]) {ok = x;} else {ng = x;}}int r = ok;L[j] = l;R[j] = r;}for (int j = 0;j <= N;j++) dp[0][j] = 1;vector<vector<mint>> S(N + 1, vector<mint>(N + 1, 0));for (int j = 0;j <= N;j++) S[0][j] = dp[0][j];for (int i = 1;i <= N;i++) {for (int j = 1;j <= N;j++) {int l = L[j];int r = R[j];dp[i][j] += dp[i][j - 1];if (i < l or r < i) continue;dp[i][j] += S[i - 1][j - 1] - (l == 1 ? 0 : S[l - 2][j - 1]);}for (int j = 0;j <= N;j++) S[i][j] = S[i - 1][j] + dp[i][j];}cout << dp[N][N].val() << endl;}