Submission #535662

#	Time	Username	Problem	Language	Result	Execution time	Memory
535662		getac	Palindromes (APIO14_palindrome)	C++14	100 / 100	27 ms	36240 KiB

palindrome

//InTheNameOfGOD
//PRS;)
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define rep(i, l, r) for(ll i = ll(l); i < ll(r); ++i)
#define per(i, l, r) for(ll i = ll(r) - 1; i >= ll(l); --i)
#define Fast cin.tie(0) -> sync_with_stdio(0);
#define min(x, y) (x < y ? x : y)
#define max(x, y) (x > y ? x : y)
typedef long long ll;
using namespace std;
constexpr int xn = 3e5 + 5;
int ng[xn][26], ans[xn], lk[xn], oc[xn], sz[xn], cnt, ti;
string s;
inline void ad(int v)
{
    while(s[v - sz[ti] - 1] != s[v]) ti = lk[ti];
    int x = lk[ti], c = s[v] - 'a';
    while(s[v - sz[x] - 1] != s[v]) x = lk[x];
    if(!ng[ti][c])
	{
        ng[ti][c] = ++cnt, sz[cnt] = sz[ti] + 2, lk[cnt] = sz[cnt] == 1 ? 2 : ng[x][c];
        ans[cnt] = ans[lk[cnt]] + 1;
    }
	ti = ng[ti][c], oc[ti]++;
}
int main()
{
	Fast
	cin >> s;
	int n = s.size();
	lk[1] = lk[2] = 1, cnt = ti = 2, sz[1] = -1, sz[2] = 0;
	rep(i, 0, n) ad(i);
	per(i, 1, cnt + 1) oc[lk[i]] += oc[i];
    ll ans = 0;
    rep(i, 2, cnt + 1) ans = max(ans, 1ll * oc[i] * sz[i]);
    cout << ans << '\n';
}

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