Submission #1211304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211304		k1r1t0	Palindromes (APIO14_palindrome)	C++20	100 / 100	50 ms	71120 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 310000;
const int K = 26;

int s[N], len[N], lnk[N], to[N][K], cnt[N], n, suff, last;

void init() {
	s[n++] = -1;
	lnk[0] = 1;
	len[1] = -1;
	last = 1;
}

int get_link(int v) {
	while (s[n - len[v] - 2] != s[n - 1])
		v = lnk[v];
	return v;
}

void add_char(int c) {
	s[n++] = c;
	suff = get_link(suff);
	if (!to[suff][c]) {
		last++;
		len[last] = len[suff] + 2;
		lnk[last] = to[get_link(lnk[suff])][c];
		to[suff][c] = last;
	}
	suff = to[suff][c];
	cnt[suff]++;
}

void count() {
	for (int i = last; i >= 0; i--)
		cnt[lnk[i]] += cnt[i];
}

int solve() {
	int ans = 0;
	for (int i = 0; i <= last; i++)
		ans = max(ans, len[i] * cnt[i]);
	return ans;
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	init();
	string s; cin >> s;
	for (char c : s)
		add_char(c - 'a');
	count();
	cout << solve();
}

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