Submission #982626

#TimeUsernameProblemLanguageResultExecution timeMemory
982626vjudge1Palindromic Partitions (CEOI17_palindromic)C++17
0 / 100
1 ms456 KiB
#include <bits/stdc++.h> #define pii pair<int,int> #define int long long #define ff first #define ss second using namespace std; void solve() { string s; cin >> s; int n = s.length(); vector<int> dp(n/2+2,0); int back = n-1; for (int i = 0; i < n/2+1; i++) { if (i >= back) break; for(int j = 0; j <= i; j++) { //cout << s.substr(j,i-j+1) << ' ' << s.substr(back,i-j+1) << " i: " << i << " j: " << j << '\n'; if (s.substr(j,i-j+1) == s.substr(back,i-j+1)) { if (j==0) dp[i] = max(dp[i],2ll); else dp[i] = max(dp[i],dp[j-1]+2); } } back--; } int ans = 1; if (n%2) { for (int i = 0; i < n/2+1; i++) { ans = max(ans,dp[i]+1); } } else { for (int i = 0; i < n/2-1; i++) { ans = max(ans,dp[i]+1); } ans = max(ans,dp[n/2-1]); } cout << ans << '\n'; } signed main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...