Submission #132743

#	Time	Username	Problem	Language	Result	Execution time	Memory
132743		Bench0310	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	653 ms	45300 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;
const int N=1000000;
const long long p=29;
const long long mod=1000000007;

long long e[N];
int n;
string s;
int dp[N];

int solve(int l,int r)
{
    if(l>r) return 0;
    if(l==r) return 1;
    if(dp[l]!=-1) return dp[l];
    int res=0;
    long long one=0,two=0;
    for(int i=0;l+i<r-i;i++)
    {
        one=((one*p)+(s[l+i]-'a'))%mod;
        two=(two+e[i]*(s[r-i]-'a'))%mod;
        if(one==two)
        {
            res=2+solve(l+i+1,r-i-1);
            break;
        }
    }
    if(res==0) res=1;
    return dp[l]=res;
}

int main()
{
    e[0]=1;
    for(int i=1;i<N;i++) e[i]=(e[i-1]*p)%mod;
    int t;
    cin >> t;
    while(t--)
    {
        cin >> s;
        n=s.size();
        memset(dp,-1,sizeof dp);
        cout << solve(0,n-1) << endl;
    }
    return 0;
}

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