Submission #868319

#	Time	Username	Problem	Language	Result	Execution time	Memory
868319		Amdadul	Palindromes (APIO14_palindrome)	C++14	0 / 100	30 ms	37984 KiB

palindrome

#include<iostream>
#include<string>
#include<vector>
using namespace std;





const int N=300000+10;

int tree[N][26];
int idx,len[N],link[N],cnt[N],t;
string s;
int oc[N];
int ans=0;

void add(int p)
{
    while(s[p-len[t]-1]!=s[p])t=link[t];
    int x=link[t];
    int c=s[p]-'a';

    while(s[p-len[x]-1]!=s[p])x=link[x];

    if(tree[t][c]==0)
    {
        tree[t][c]=++idx;
        len[idx]=len[t]+2;
        link[idx]=len[idx]==1?2:tree[x][c];
        oc[idx]++;
    }
    else oc[tree[t][c]]++;
    t=tree[t][c];


}




int main()
{

    len[1]=-1,link[1]=1;
    len[2]=0,link[2]=1;
    idx=t=2;


    cin>>s;
    s='$'+s;
    for(int i=1; i<(int)s.size(); i++)
    {
        add(i);
    }
    long long ans=0;
    vector<int>fre(s.size()+5,0);
    for(int i=(int)s.size()+4; i>=1; i--)
    {
        if(fre[i])continue;

        int x=i;
        long long  tot=0;
        while(x>1)
        {
            tot+=oc[x];
            ans=max(ans,1ll*len[x]*tot);
            fre[x]=1;
            x=link[x];
        }
    }
    cout<< ans <<"\n";

}

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