結果

問題 No.1378 Flattening
ユーザー 00 Sakuda00 Sakuda
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0