Submission #1207929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207929		A_M_Namdar	Palindromes (APIO14_palindrome)	C++20	23 / 100	1097 ms	840 KiB

palindrome

#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();
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27