oj.uz

Submission #960977

# Submission time Handle Problem Language Result Execution time Memory
960977 2024-04-11T10:24:43 Z Ghetto Palindromic Partitions (CEOI17_palindromic) C++17
35 / 100
 10000 ms 868 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 9 ms 348 KB Output is correct
7 Correct 5 ms 468 KB Output is correct
8 Correct 8 ms 348 KB Output is correct
9 Correct 8 ms 472 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 9 ms 348 KB Output is correct
7 Correct 5 ms 468 KB Output is correct
8 Correct 8 ms 348 KB Output is correct
9 Correct 8 ms 472 KB Output is correct
10 Execution timed out 10048 ms 868 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 9 ms 348 KB Output is correct
7 Correct 5 ms 468 KB Output is correct
8 Correct 8 ms 348 KB Output is correct
9 Correct 8 ms 472 KB Output is correct
10 Execution timed out 10048 ms 868 KB Time limit exceeded
11 Halted 0 ms 0 KB -