제출 #934256

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
934256		UmairAhmadMirza	Palindromic Partitions (CEOI17_palindromic)	C++14	60 / 100	655 ms	4420 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
#define int long long
int const N=10005;
int const mod=1e9+7;
int const base=727;
int dp[N];
int Hash[N];
int pw[N];
void pre(){
  pw[0]=1;
  for(int i=1;i<N;i++)
    pw[i]=(pw[i-1]*base)%mod;
}
int make_hash(int l,int r){
  l--;
  int h=((Hash[r]-((Hash[l]*pw[r-l])%mod))+mod)%mod;
  return h;
}
void solve(){
  string s;
  cin>>s;
  int n=s.length();
  int hsh=0;
  for(int i=0;i<n;i++){
    hsh*=base;
    hsh%=mod;
    hsh+=s[i];
    hsh%=mod;
    Hash[i+1]=hsh;
  }
  for(int i=0;i<=n;i++)
    dp[i]=0;
  int ans=0;
  for(int i=1;i<=(n/2);i++){
    dp[i]=-1;
    for(int j=0;j<i;j++)
      if(make_hash(j+1,i)==make_hash(n-(i-1),n-(j))&& dp[j]>-1)
        dp[i]=max(dp[i],dp[j]+2);
    // cout<<dp[i]<<endl;
    ans=max(ans,dp[i]+(i*2<n));
  }
  cout<<max(1LL,ans)<<endl;
}
signed main(){
  pre();
  int t;
  cin>>t;
  while(t--)
    solve();
  return 0;
}

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