Submission #47225

#	Time	Username	Problem	Language	Result	Execution time	Memory
47225		robert	Palindromic Partitions (CEOI17_palindromic)	C++14	60 / 100	10023 ms	40556 KiB

palindromic

#include <iostream>
#include <cstring>

using namespace std;

string s;
int N;
int m[1000100];

int solve(int n){
	if(N-n-1<n)
		return 0;
	if(m[n]!=-1)
		return m[n];
	int sol = 1;
	for(int x=N-n-1; x>=n; x--){
		if(s[x]==s[n]){
			//possible beginning of palindromic sequence
			bool m = 1;
			for(int y=0; y+x<=N-n-1; y++){
				if(s[y+x]!=s[n+y])
					m = 0;
			}
			if(m&&x!=n){
				sol = max(sol, 2+solve(N-x));
				break;
			}
		}
	}
	return m[n] = sol;
}

int main(){
	int T; cin>>T;
	while(T--){
		cin>>s;
		N = s.length();
		memset(m, -1, sizeof(m));
		cout << solve(0) << endl;	
	}
	return 0;
}

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