Submission #900046

#	Time	Username	Problem	Language	Result	Execution time	Memory
900046		1075508020060209tc	Palindromes (APIO14_palindrome)	C++14	0 / 100	1022 ms	131072 KiB

palindrome

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
#define SZ(x) (int)(x).size()
const int mod=1e9+9;
int qpow(int x,int t){
if(t==0){return 1;}
if(t%2==1){return qpow(x,t-1)*x%mod;}
int xx=qpow(x,t/2);
return xx*xx%mod;
}
int tme[500005];
struct rlhsh{
vector<int>hsh;
int n;
void init(string s){
n=s.size();
hsh.resize(s.size()+10,0);
for(int i=1;i<=n;i++){
    hsh[i]=(hsh[i-1]+(s[i-1]-'a')*tme[i])%mod;
}
}
int gthsh(int l,int r){
int ret=(hsh[r]-hsh[l-1]+mod)*qpow(tme[l-1],mod-2)%mod;
return ret;
}
};

int n;

pair<int,int>rev(int l,int r){
l=n-l+1;r=n-r+1;
swap(l,r);
return {l,r};
}

string s;

signed main(){

tme[0]=1;
for(int i=1;i<=500000;i++){
    tme[i]=tme[i-1]*378%mod;
}

cin>>s;
map<string,int>mp;
int ans=1;
n=s.size();
s="*"+s;
for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
        int ok=1;
        int r=j;
        string t="";
        for(int k=i;k<=j;k++){
            if(s[k]!=s[r]){
                ok=0;
            }
            t+=s[k];
            r--;
        }
        if(ok){
            mp[t]++;
            ans=max(ans,mp[t]*(j-i+1));
        }

    }
}
cout<<ans<<"\n";



}

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