Submission #933648

#TimeUsernameProblemLanguageResultExecution timeMemory
933648mgchRound words (IZhO13_rowords)C++14
48 / 100
2019 ms17492 KiB
#include <bits/stdc++.h> using namespace std; /** so there is complicated algo based on some research let's get it later * * * you have to get that |lcs(a, b) - lcs(a, b[1..n-1] + b[0])| <= 2 * so if you have ans >= lcs(a, b) + 2 then ... push it * */ const int N = 2024; int dp[N][N], gr[N], n, m; string s[N], t[N]; int lcs(const string &a, const string &b) { for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]); if (a[i] == b[j]) { dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1); } } } return dp[n][m]; } int main() { // freopen("rowords.in", "r", stdin); freopen("rowords.out", "w", stdout); string a, b; getline(cin, a); getline(cin, b); if (a.length() < b.length()) { swap(a, b); } n = a.length(); m = b.length(); int ans = 0; for (int i = 0; i < n; ++i) { s[i] = a.substr(i) + a.substr(0, i); } vector <pair <int, int> > all; for (int i = 0; i < m; ++i) { t[i] = b.substr(i) + b.substr(0, i); for (int j = 0; j < m; ++j) { if (gr[i] < n && t[i][j] == a[gr[i]]) { ++gr[i]; } } all.push_back(make_pair(-gr[i], i)); } sort(all.rbegin(), all.rend()); for (int i = 0; i < 1; ++i) { for (int jj = 0; jj < m && jj < ((int)5e8) / (n * m); ++jj) { int j = all[jj].second; ans = max(ans, lcs(s[i], t[j])); } } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...