oj.uz

Submission #916363

# Submission time Handle Problem Language Result Execution time Memory
916363 2024-01-25T18:21:51 Z vjudge1 Palindromic Partitions (CEOI17_palindromic) C++11
0 / 100
 1 ms 348 KB 
#include <iostream>
#include <vector>
#include <string>

bool isPalindrome(const std::string& str) {
    int start = 0;
    int end = str.size() - 1;
    
    while (start < end) {
        if (str[start] != str[end]) {
            return false;
        }
        start++;
        end--;
    }
    
    return true;
}

int maxPalindromicPartitions(const std::string& s) {
    int n = s.size();
    if (n == 0) return 0;

    std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));

    for (int i = 0; i < n; ++i)
        dp[i][i] = 1;

    for (int cl=2; cl<=n; ++cl)
        for (int i=0; i<n-cl+1; ++i){
            int j = i+cl-1;
            if (isPalindrome(s.substr(i, cl)) && cl == j-i+1)
                dp[i][j] = 1;
            else
                dp[i][j] = std::max(dp[i][j-1], dp[i+1][j]);
        }

   return dp[0][n-1];
}

int main() {
   int t;
   std::cin >> t;

   while(t--) {
       std::string s;
       std::cin >> s;

       std::cout << maxPalindromicPartitions(s) << '\n';
   }

   return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -