Submission #916363

#	Time	Username	Problem	Language	Result	Execution time	Memory
916363		vjudge1	Palindromic Partitions (CEOI17_palindromic)	C++11	0 / 100	1 ms	348 KiB

palindromic

#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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40