제출 #1207929

#제출 시각아이디문제언어결과실행 시간메모리
1207929A_M_NamdarPalindromes (APIO14_palindrome)C++20
23 / 100
1097 ms840 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast,unroll-loops") using namespace std; const int N = 1e4 + 10, p = 1e9 + 207; int n, h1[N], h2[N], pw[N]; string s; unordered_map<int, int> cnt; int mul(int a, int b) { return 1ll * a * b % p; } int sum(int a, int b) { a += b; if (a < 0) a += p; if (a >= p) a -= p; return a; } int get1(int l, int r) { int res = h1[r]; res = sum(res, -mul(pw[r - l], h1[l])); return res; } int get2(int l, int r) { int res = h2[l]; res = sum(res, -mul(pw[r - l], h2[r])); return res; } void input() { cin >> s; n = s.size(); } void solve() { pw[0] = 1; for (int i = 1; i < N; i++) pw[i] = mul(pw[i - 1], 30); for (int i = 0; i < n; i++) { h1[i + 1] = mul(h1[i], 30); h1[i + 1] = sum(h1[i + 1], s[i] - 'a' + 1); } for (int i = n - 1; i >= 0; i--) { h2[i] = mul(h2[i + 1], 30); h2[i] = sum(h2[i], s[i] - 'a' + 1); } int ans = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j <= n; j++) { if (get1(i, j) == get2(i, j)) { int tmp = get1(i, j); cnt[tmp] += j - i; ans = max(ans, cnt[tmp]); } } } cout << ans; } int main() { ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0); input(); solve(); }
#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...