Submission #933639

#TimeUsernameProblemLanguageResultExecution timeMemory
933639mgchRound words (IZhO13_rowords)C++14
16 / 100
2100 ms14752 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], n, m; 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); n = a.length(); m = b.length(); int ans = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { ans = max(ans, lcs(a.substr(i) + a.substr(0, i), b.substr(j) + b.substr(0, j))); } } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...