Submission #538713

#	Time	Username	Problem	Language	Result	Execution time	Memory
538713		radal	Palindromes (APIO14_palindrome)	C++17	100 / 100	28 ms	35084 KiB

palindrome

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 3e5+20,mod = 1e9+7,inf = 1e9+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}

inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    }
    return z;
}
int tr[N][26],n,sz[N],cur,mx,suf[N],ans[N];
string s;
inline void add_to_tree(int i){
    while (i-sz[cur]-1 < 0 || s[i] != s[i-sz[cur]-1]){
        cur = suf[cur];
    }
    int c = s[i]-'a';
    if (!tr[cur][c]){
        mx++;
        tr[cur][c] = mx;
        sz[mx] = sz[cur]+2;
        int nxt = suf[cur];
        while (s[i] != s[i-sz[nxt]-1]) nxt = suf[nxt];
        if (sz[mx] > 1) suf[mx] = tr[nxt][c];
        else suf[mx] = 1;
        cur = mx;
        ans[mx]++;
    }
    else{
        cur = tr[cur][c];
        ans[cur]++;
    }
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> s;
    n = s.size();
    sz[0] = -1;
    sz[1] = 0;
    cur = 1;
    mx = 1;
    suf[1] = 0;
    suf[0] = 0;
    rep(i,0,n){
        add_to_tree(i);
    }
    ll ANS = 0;
    repr(i,mx,1){
        ans[suf[i]] += ans[i];
        ANS = max(ANS,1ll*ans[i]*sz[i]);
    }
    cout << ANS;
}

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