Submission #1001688

#TimeUsernameProblemLanguageResultExecution timeMemory
1001688vjudge1Dabbeh (INOI20_dabbeh)C++17
25 / 100
1638 ms6740 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define inf 0x3F3F3F3F const int MXN = 3e5 + 5; const int mod = 1e9 + 7; int b1, b2; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int dp[505][505]; int R[505]; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); for (int i = 0; i < 505; i++) for (int j = 0; j < 505; j++) dp[i][j] = -1; int k, m; cin >> k >> m; string t[k]; for (int i = 0; i < k; i++) cin >> t[i]; string s; cin >> s; int n = s.length(); s = "#" + s; for (int i = 1; i <= n; i++) { for (int j = 0; j < k; j++) { for (int l = i; l <= n; l++) { if (s[l] != t[j][l - i]) break; R[i] = max(R[i], l); } } } for (int sz = 1; sz <= n; sz++) { for (int i = 1; i + sz - 1 <= n; i++) { int j = i + sz - 1; if (R[i] >= j) dp[i][j] = 1; else dp[i][j] = inf; for (int k = i; k < j; k++) { dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]); } } } for (int i = 0; i < m; i++) { int l, r; cin >> l >> r; l++; cout << (dp[l][r] == inf ? -1 : dp[l][r]) << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...