Submission #1243418

#TimeUsernameProblemLanguageResultExecution timeMemory
1243418chr34Round words (IZhO13_rowords)C++20
40 / 100
2096 ms448 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define endl "\n" #define dbg(x) cout << #x << " = " << (x) << endl; const int INF = 1e18; const int MAXN = 1e6 + 10; const int MOD = 1e9 + 7; int lcs(const string& a, const string& b) { int n = a.size(), m = b.size(); vector<vector<int>> dp(2, vector<int>(m + 1, 0)); for (int i = 1; i <= n; ++i) { int cur = i % 2, prev = 1 - cur; for (int j = 1; j <= m; ++j) { if (a[i - 1] == b[j - 1]) dp[cur][j] = dp[prev][j - 1] + 1; else dp[cur][j] = max(dp[prev][j], dp[cur][j - 1]); } } return dp[n % 2][m]; } int32_t main(){ ios::sync_with_stdio(false); cin.tie(nullptr); //freopen("input.in", "r", stdin); //freopen("input.out", "w", stdout); string s1, s2; cin >> s1 >> s2; int maxLCS = 0; string s1r = s1; reverse(s1r.begin(), s1r.end()); string s2r = s2; reverse(s2r.begin(), s2r.end()); string s2_doubled = s2 + s2; string s2r_doubled = s2r + s2r; int len = s2.size(); for (int i = 0; i < len; ++i) { string rot_s2 = s2_doubled.substr(i, len); string rot_s2r = s2r_doubled.substr(i, len); maxLCS = max(maxLCS, lcs(s1, rot_s2)); maxLCS = max(maxLCS, lcs(s1r, rot_s2)); maxLCS = max(maxLCS, lcs(s1, rot_s2r)); maxLCS = max(maxLCS, lcs(s1r, rot_s2r)); } cout << maxLCS << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...