제출 #134960

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
134960		fredbr	회문 (APIO14_palindrome)	C++17	0 / 100	2 ms	456 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int const p = 31;
int const mod = 1e9 + 9;
int const maxn = 10010;

char s[maxn];
int h[maxn];
int pw[maxn];

vector<int> hs(int n) {
    vector<int> res(n+1);

    for (int i = 1; i <= n; i++) {
        res[i] = (ll(res[i-1])*p + s[i] ) % mod;
    }

    return res;
}

void init() {
    pw[0] = 1;
    for (int i = 1; i < maxn; i++)
        pw[i] = ll(pw[i-1])*p%mod;
}

int main() {
    init();

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) cin >> s[i];

    auto fh = hs(n);

    reverse(s+1, s+n+1);

    auto rh = hs(n);

    // ll ans = 0;

    auto comp = [&] (int l, int r) -> pair<int, int> {
        int x = ((ll(fh[r]) -     ll(fh[l-1])*pw[r-l+1]) % mod + mod) % mod;
        int y = ((ll(rh[n-l+1]) - ll(rh[n-r])*pw[r-l+1]) % mod + mod) % mod;

        return {x == y, x};
    };

    ll ans = 0;

    for (int lenght = 1; lenght <= n; lenght++) {
        vector<int> v;
        for (int l = 1; l + lenght - 1 <= n; l++) {
            int r = l + lenght - 1;

            auto x = comp(l, r);
            if (x.first) {
                v.push_back(x.second);
            }
        }

        sort(v.begin(), v.end());

        int best = 0;
        for (int i = 0; i < (int)v.size(); i++) {
            int l = i;
            while (i < (int)v.size() and (i == 0 or v[i] == v[i-1])) i++;
            best = max(best, i - l);
        }

        ans = max(ans, ll(lenght)*best);
        // cout << lenght << " " << best << "\n";
    }

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

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