Submission #960977

#	Time	Username	Problem	Language	Result	Execution time	Memory
960977		Ghetto	Palindromic Partitions (CEOI17_palindromic)	C++17	35 / 100	10048 ms	868 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e4 + 5;

int t;

int n;
char ch[MAX_N];

int dp[MAX_N];

void do_tc(int tc) {
    string str; cin >> str;
    n = str.size();
    for (int i = 1; i <= n; i++) ch[i] = str[i - 1];

    for (int len = n; len >= 0; len--) {
        int l = 1 + len, r = n - len;
        if (l > r) continue;

        dp[len] = 1;
        string l_str = "", r_str = "";

        for (int i = 1; i <= n; i++) {
            int new_l = l - 1 + i, new_r = r + 1 - i;
            if (new_l >= new_r) break;

            l_str = l_str + ch[new_l];
            r_str = ch[new_r] + r_str;

            if (l_str != r_str) continue;
            dp[len] = max(dp[len], 2 + ((new_l + 1 == new_r) ? 0 : dp[len + i]));
        }

        // cout << len << ": " << dp[len] << endl;
    }

    cout << dp[0] << '\n';
}

int main() {
    // freopen("part.in", "r", stdin);

    cin.sync_with_stdio(false);
    cin.tie(0);

    cin >> t;
    for (int i = 1; i <= t; i++) do_tc(i);
}

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40