Submission #511572

#	Time	Username	Problem	Language	Result	Execution time	Memory
511572		Monarchuwu	Palindromic Partitions (CEOI17_palindromic)	C++17	60 / 100	10020 ms	22052 KiB

palindromic

#include<iostream>
#include<algorithm>
#include<string>
#include<bitset>
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

const int N = 1e6 + 16, mod = 1e9 + 7, base = 331;
const ll mod2 = (ll)mod * mod;
int n;
string s;
ll pw[N], hsh[N];
ll get(int l, int r) {
    return (hsh[r] - hsh[l - 1] * pw[r - l + 1] + mod2) % mod;
}

int dp[N];
int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    pw[0] = 1;
    for (int i = 1; i < N; ++i)
        pw[i] = pw[i - 1] * base % mod;

    int test; cin >> test; while (test--) {
        cin >> s; n = s.size();
        s = " " + s;

        for (int i = 1; i <= n; ++i)
            hsh[i] = (hsh[i - 1] * base + s[i]) % mod;

        fill(dp + 1, dp + n + 1, -N);
        for (int i = 1; i <= n / 2; ++i)
            for (int j = 1; j <= i; ++j)
                if (get(j, i) == get(n - i + 1, n - j + 1))
                    dp[i] = max(dp[i], dp[j - 1] + 2);

        int ans(1);
        for (int i = 1; i <= n / 2; ++i) {
            ans = max(ans, dp[i] + (i * 2 == n ? 0 : 1));
        }
        cout << ans << '\n';
    }
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/
/*
==================================================+
INPUT:                                            |
--------------------------------------------------|
4
bonobo
deleted
racecar
racecars
--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|
3
5
7
1
--------------------------------------------------|
==================================================+
*/

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40