Submission #1166092

#TimeUsernameProblemLanguageResultExecution timeMemory
1166092JelalTkmPalindromes (APIO14_palindrome)C++20
23 / 100
1096 ms19300 KiB
#include <bits/stdc++.h> #pragma GCC optimize ("O3") #pragma GCC target ("sse4") using namespace std; #define int long long int const int N = 1e5 + 10; const int md = 1e9 + 7; const int INF = 1e18; int32_t main(int32_t argc, char *argv[]) { ios::sync_with_stdio(false); cin.tie(nullptr); int T = 1; // cin >> T; while (T--) { string s; cin >> s; int n = (int) s.size(); s = '#' + s; vector<vector<bool>> dp(n + 1, vector<bool> (n + 1)); vector<int> sz(n + 1); unordered_map<string, int> mp; int ans = 0; for (int i = 1; i <= n; i++) { dp[i][i] = 1; sz[i] = 1; string c = ""; c += s[i]; mp[c]++; ans = max(ans, mp[c]); for (int j = i - 1; j >= 1; j--) { c = s[j] + c; if (j == i - 1) { if (s[j] == s[i]) { int cnt = (++mp[c]); sz[j] = 2; dp[j][i] = 1; ans = max(ans, cnt * sz[j]); } } else if (s[i] == s[j] && dp[j + 1][i - 1]) { int cnt = (++mp[c]); sz[j] = (i - j + 1); dp[j][i] = 1; ans = max(ans, sz[j] * cnt); } } } cout << ans << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...