Submission #1011317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011317		Irate	Palindromic Partitions (CEOI17_palindromic)	C++17	60 / 100	10088 ms	14356 KiB

palindromic

#include<bits/stdc++.h>
using namespace std;
const int mxN = 1e6 + 6;
const int base = 53;
const int MOD = 1e9 + 7;
int H[mxN], P[mxN];
int get_hash(int l, int r){
    return (1LL * H[r] - 1LL * H[l - 1] * P[r - l + 1] % MOD + MOD) % MOD;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    P[0] = 1;
    for(int i = 1;i < mxN;++i){
        P[i] = 1LL * P[i - 1] * base % MOD;
    }
    int t;
    cin >> t;
    while(t--){
        string str;
        cin >> str;
        int n = (int)str.size();
        str = '$' + str;
        for(int i = 1;i <= n;++i){
            H[i] = (1LL * H[i - 1] * base % MOD + (str[i] - 'a' + 1)) % MOD;
        }
        vector<int>dp(n + 1, 1);
        dp[n / 2] = n % 2;
        for(int i = n / 2 - 1;i >= 0;--i){
            for(int j = 1;2 * j <= n - 2 * i;++j){
                // cout << i << ": " << j << "\n";
                if(get_hash(i + 1, i + j) == get_hash(n - i - j + 1, n - i))dp[i] = max(dp[i], dp[i + j] + 2);
            }
            // cout << i << ": dp = " << dp[i] << '\n';  
        }
        cout << dp[0] << '\n';
    }
}

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