Submission #499857

#	Time	Username	Problem	Language	Result	Execution time	Memory
499857		pooyashams	Palindromic Partitions (CEOI17_palindromic)	C++14	60 / 100	560 ms	49396 KiB

palindromic

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int maxn = 5010;

short dp[maxn];
short mxl[maxn][maxn];
int n;
string s;

inline void fill_mxl()
{
	int mid = n/2;
	for(int i = mid-1; i >= 0; i--)
	{
		for(int j = n-1; j >= mid; j--)
		{
			mxl[i][j-mid] = 0;
			if(s[i] == s[j])
			{
				if(i == mid-1 or j == n-1)
					mxl[i][j-mid] = 1;
				else
					mxl[i][j-mid] = 1+mxl[i+1][j-mid+1];
			}
		}
	}
}

inline void fill_dp()
{
	int mid = n/2;
	if(n & 1)
		dp[mid] = 1;
	else
		dp[mid] = 0;
	for(int i = mid-1; i >= 0; i--)
	{
		dp[i] = 1;
		for(int j = i; j < mid; j++)
		{
			if(mxl[i][n-1-j-mid] >= j-i+1)
				dp[i] = max(dp[i], (short)(dp[j+1]+2) );
		}
	}
	//for(int i = 0; i < mid; i++)
	//	cerr << dp[i] << " ";
	//cerr << endl;
}

inline void solve()
{
	cin >> s;
	n = s.size();
	fill_mxl();
	fill_dp();
	cout << dp[0] << endl;
}

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T; cin >> T;
	while(T--)
	{
		solve();
	}
	return 0;
}

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