Submission #1346573

#TimeUsernameProblemLanguageResultExecution timeMemory
1346573killerzaluuPalindromes (APIO14_palindrome)C++20
23 / 100
1095 ms1092 KiB
#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    int n = (int)s.size();

    const ull base = 911382323ull;

    vector<ull> pw(n + 1), h1(n + 1), h2(n + 1);
    pw[0] = 1;

    for (int i = 1; i <= n; i++) pw[i] = pw[i - 1] * base;

    for (int i = 1; i <= n; i++) {
        h1[i] = h1[i - 1] * base + (s[i - 1] - 'a' + 1);
    }

    string t = s;
    reverse(t.begin(), t.end());

    for (int i = 1; i <= n; i++) {
        h2[i] = h2[i - 1] * base + (t[i - 1] - 'a' + 1);
    }

    auto get1 = [&](int l, int r) -> ull {
        return h1[r] - h1[l - 1] * pw[r - l + 1];
    };

    auto get2 = [&](int l, int r) -> ull {
        return h2[r] - h2[l - 1] * pw[r - l + 1];
    };

    auto ispal = [&](int l, int r) -> bool {
        int rl = n - r + 1;
        int rr = n - l + 1;
        return get1(l, r) == get2(rl, rr);
    };

    map<pair<ull,int>, int> mp;

    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            if (ispal(i, j)) {
                mp[{get1(i, j), j - i + 1}]++;
            }
        }
    }

    long long ans = 0;
    for (auto x : mp) {
        ans = max(ans, 1LL * x.first.second * x.second);
    }

    cout << ans << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...