oj.uz

Submission #934256

# Submission time Handle Problem Language Result Execution time Memory
934256 2024-02-27T04:24:40 Z UmairAhmadMirza Palindromic Partitions (CEOI17_palindromic) C++14
60 / 100
 655 ms 4420 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 655 ms 672 KB Output is correct
11 Correct 333 ms 724 KB Output is correct
12 Correct 589 ms 720 KB Output is correct
13 Correct 421 ms 600 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 655 ms 672 KB Output is correct
11 Correct 333 ms 724 KB Output is correct
12 Correct 589 ms 720 KB Output is correct
13 Correct 421 ms 600 KB Output is correct
14 Runtime error 16 ms 4420 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -