oj.uz

Submission #934245

# Submission time Handle Problem Language Result Execution time Memory
934245 2024-02-27T04:02:56 Z UmairAhmadMirza Palindromic Partitions (CEOI17_palindromic) C++17
35 / 100
 125 ms 2136 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int const N=305;
int const mod=1e9+7;
int const base=727;
int dp[N][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=1;i<=n;i++)
    for(int j=i;j<=n;j++)
      dp[i][j]=1;
  for(int l=1;l<n;l++)
    for(int i=1;i<=n-l;i++){
      for(int x=0;x<((l+1)/2);x++)
        if(make_hash(i,i+x)==make_hash((i+l)-x,i+l))
          dp[i][i+l]=max(dp[i][i+l],2+dp[(i+x)+1][((i+l)-x)-1]);
    }
  cout<<dp[1][n]<<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 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 424 KB Output is correct
5 Correct 1 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 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 424 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 125 ms 1116 KB Output is correct
7 Correct 53 ms 1100 KB Output is correct
8 Correct 98 ms 1116 KB Output is correct
9 Correct 75 ms 860 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 424 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 125 ms 1116 KB Output is correct
7 Correct 53 ms 1100 KB Output is correct
8 Correct 98 ms 1116 KB Output is correct
9 Correct 75 ms 860 KB Output is correct
10 Runtime error 2 ms 2136 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 424 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 125 ms 1116 KB Output is correct
7 Correct 53 ms 1100 KB Output is correct
8 Correct 98 ms 1116 KB Output is correct
9 Correct 75 ms 860 KB Output is correct
10 Runtime error 2 ms 2136 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -