Submission #856326

#TimeUsernameProblemLanguageResultExecution timeMemory
856326CyanmondPalindromic Partitions (CEOI17_palindromic)C++17
35 / 100
10037 ms676 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i, l, r) for (int i = (l); i < (r); ++i) #define per(i, l, r) for (int i = (r - 1); i >= l; --i) #define ALL(x) (x).begin(), (x).end() using i64 = long long; void main_() { string S; cin >> S; const int N = (int)S.size(); string A = S.substr(0, N / 2), B = S.substr(N - N / 2, N / 2); reverse(ALL(B)); const int M = (int)A.size(); vector<int> dp(M + 1, -(2 * N)); dp[0] = 0; rep(i, 0, M) { string x, y; rep(j, i, M) { x += A[j]; y = B[j] + y; if (x == y) { dp[j + 1] = max(dp[j + 1], dp[i] + 2); } } } for (auto &e : dp) ++e; if (N % 2 == 0) --dp[M]; cout << *max_element(ALL(dp)) << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) main_(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...