Submission #1207926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207926		A_M_Namdar	Palindromes (APIO14_palindrome)	C++20	23 / 100	416 ms	23384 KiB

palindrome

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;

const int N = 1e4 + 10, p = 2e7 + 33;
int n, h1[N], h2[N], pw[N], cnt[p];
string s;

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], 28);
	for (int i = 0; i < n; i++) {
		h1[i + 1] = mul(h1[i], 28);
		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], 28);
		h2[i] = sum(h2[i], s[i] - 'a' + 1);
	}
	int ans = 0;
	for (int len = 1; len <= n && len * (n - len + 1) > ans; len++) {
		for (int i = 0; i + len <= n; i++) {
			int j = i + len;
			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