Submission #290394

#	Time	Username	Problem	Language	Result	Execution time	Memory
290394		ZwariowanyMarcin	Palindromes (APIO14_palindrome)	C++17	100 / 100	30 ms	34944 KiB

palindrome

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ss(x) (int) x.size()
#define cat(x) cerr << #x << " = " << x << endl

using ll = long long;

using namespace std;

const int N = 3e5 + 100;
const int A = 26;

int cnt, len[N], link[N], last, nxt[N][A], q[N];

char s[N];

void add(int x) {
	int v = last, c = s[x] - 'a';
	while (s[x] != s[x - len[v] - 1]) v = link[v];
		
	if (!nxt[v][c]) {
		int ja = ++cnt, k = link[v];
		len[ja] = len[v] + 2;
		while (s[x] != s[x - len[k] - 1]) k = link[k];
		link[ja] = nxt[k][c], nxt[v][c] = ja;
	}
	q[nxt[v][c]]++;
	last = nxt[v][c];
}		

int main() {
	len[1] = -1;
	link[0] = link[1] = 1;
	cnt = 1;
	last = 0;
	
	scanf ("%s", s + 1);
	int n = strlen(s + 1);
	for (int i = 1; i <= n; ++i)
		add(i);
		
	ll out = 0;
	for (int i = cnt; 2 <= i; --i) {
		out = max(out, ll(len[i]) * q[i]);
		q[link[i]] += q[i];
	}
	printf ("%lld\n", out);
	
	return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |  scanf ("%s", s + 1);
      |  ~~~~~~^~~~~~~~~~~~~

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