Submission #939059

#TimeUsernameProblemLanguageResultExecution timeMemory
939059huyboyPalindromic Partitions (CEOI17_palindromic)C++17
35 / 100
836 ms131072 KiB
#include "bits/stdc++.h" using namespace std; void solve(){ string s; cin >> s; int n = s.size(); int dp[n + 1][n + 1]; for(int i = 0;i < n + 1;i++){ for(int j = i;j < n + 1;j++){ dp[i][j] = 1; } for(int j = 0;j < i;j++){ dp[i][j] = 0; } } for(int l = n - 1;l >= 0;l--){ for(int r = l;r <= n - 1;r++){ string suff = ""; string pref = ""; int nl = l,nr = r; while(nl < nr){ pref += s[nl]; suff = s[nr] + suff; if(pref == suff){ dp[l][r] = max(dp[l][r],dp[nl + 1][nr - 1] + 2) ; } nl++; nr--; } } } cout << dp[0][n - 1] << "\n"; } //(h[i] - h[j]) * (h[i] - h[j]) + pref[i] - pref[j + 1] signed main(){ ios_base::sync_with_stdio(0); cin.tie(0),cout.tie(0); int t = 1; cin >> t; while(t--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...