Submission #647114

#	Time	Username	Problem	Language	Result	Execution time	Memory
647114		google	Palindromes (APIO14_palindrome)	C++17	0 / 100	370 ms	2468 KiB

palindrome

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll P = 31,mxn = 10005,m = 1e9+7;
ll h[mxn],pows[mxn],N;
ll fin(int l, int r, bool rev = 0){
    ll ans;
    if (rev) {
        l = N-l-1;
        r = N-r-1;
        swap(l,r);
    }
    ans = h[r]-(l?h[l-1]:0);
    ans = (ans*pows[N-r-1])%m;
    return ans;
}
bool eq(int l1,int r1,int l2,int r2){
    if (r1-l1 != r2-l2) return 0;
    return fin(l1,r1,0) == fin(l2,r2,1);
}
map<ll,pair<ll,ll>> pa;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    string s; cin >> s;
    N = int(s.size());
    for (int i = 0;i<N;i++){
        if (i){
            pows[i] = (pows[i-1]*P)%m;
            h[i] = h[i-1];
        }
        else{
            pows[i] = 1;
            h[i] = 0;
        }
        h[i] += pows[i]*(s[i]-'a'+1); 
    }
    for (int i = 0;i<N;i++){
        for (int j = 0;j<=i;j++){
            if (fin(j,i) == fin(j,i,1)){
                ll t = fin(i,j);
                pa[t].first++;
                pa[t].second = (i-j+1);
            }
        }
    }
    ll ans = 0;
    for (auto [a,b]:pa){
        ans = max(ans,b.first*b.second);
    }
    cout << ans;
    return 0;
}

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