# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1248074 | nhnguyen14 | Palindromic Partitions (CEOI17_palindromic) | C++20 | 110 ms | 196608 KiB |
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
template<class X,class Y>
bool minimize(X &x,Y y){
if (x>y) return x=y,true; return false;
}
template<class X,class Y>
bool maximize(X &x,Y y){
if (x<y) return x=y,true; return false;
}
const int N=(int)1e4;
const int inf = (int)1e9+7;
int dp[N+2][N+2];
int n;
void reset(int _length){
for(int i=0;i<=_length+1;++i){
for(int j=0;j<=_length+1;++j) dp[i][j] = -inf;
}
return ;
}
int p[N+2]={} , h[N+2]= {};
const int base = 256;
const int MOD = 1e9+9;
string s;
int Get(int l,int r){
return ((LL)h[r] - (LL)p[r-l+1] * h[l - 1] + (LL)MOD*MOD) % MOD;
}
void solve(){
cin>>s; s = '#' + s;
n = s.size() - 1;
reset(n);
p[0] = 1;
for(int i=1;i<=n;++i) {
p[i] = (LL)p[i-1]*base % MOD;
h[i] = ((LL)h[i-1]*base+s[i]) % MOD;
}
dp[0][n+1]=0;
for(int start = 1; start <= n; ++start){
for(int finish = start;finish<=n;++finish){
int match_finish = n - start + 1 , match_start = n - finish + 1;
if (match_start <= finish) continue;
if (Get(start,finish)!=Get(match_start,match_finish)) continue;
// cerr<<start<<' '<<finish<<' '<<match_start << ' '<<match_finish<<'\n';
maximize(dp[finish][match_start] , dp[start - 1][match_finish+1] + 2);
}
}
int ans = 0;
for(int start = 1;start<=n;++start){
for(int finish = start; finish<=n;++finish){
maximize(ans , dp[start - 1][finish + 1] + 1);
maximize(ans , dp[start][finish]);
}
}
cout<<ans<<'\n';
return ;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0) ; cout.tie(0) ;
#define name "main"
if (fopen(name".inp","r")){
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
int test; cin>>test;
while(test--) solve();
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |