Submission #617024

#	Time	Username	Problem	Language	Result	Execution time	Memory
617024		Drew_	Palinilap (COI16_palinilap)	C++17	17 / 100	42 ms	468 KiB

palinilap

#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define f1 first
#define s2 second

using ii = pair<int, int>;

const int MAX = 107;


int N;
char s[MAX];

// ii dp[MAX][MAX][2];
// inline ii solve(int l, int r, bool x)
// {
// 	if (dp[l][r][x].f1 != -1)
// 		return dp[l][r][x];
// 	if (l > r)
// 		return { 0, true };
// 	if (l == r)
// 		return { 1, true };

// 	if (s[l] == s[r])
// 	{
// 		ii a = solve(l+1, r, x);
// 		ii b = solve(l, r-1, x);
// 		ii c = solve(l+1, r-1, x);

// 		return dp[l][r][x] = {a.f1 + b.f1 - c.f1 + c.s2, c.s2};
// 	}

// 	if (x)
// 	{
// 		ii p, q;
			
// 		{
// 			ii a = solve(l+1, r, x);
// 			ii b = solve(l, r-1, x);
// 			ii c = solve(l+1, r-1, x);
// 			p = { a.f1 + b.f1 - c.f1, false };
// 		}
// 		{
// 			ii a = solve(l+1, r, false);
// 			ii b = solve(l, r-1, false);
// 			ii c = solve(l+1, r-1, false);
// 			q = { a.f1 + b.f1 - c.f1 + c.s2, c.s2 };
// 		}
// 		return max(p, q);
// 	}
// 	else
// 	{
// 		ii a = solve(l+1, r, x);
// 		ii b = solve(l, r-1, x);
// 		ii c = solve(l+1, r-1, x);

// 		return dp[l][r][x] = {a.f1 + b.f1 - c.f1 + c.s2, false};
// 	}
// }

int solve()
{
	int dp[MAX][MAX];
	const auto calc = [&]() -> int
	{
		memset(dp, 0, sizeof(dp));
		
		for (int i = 0; i < N; ++i)
			dp[i][i] = true, dp[i][i+1] = true;

		for (int len = 2; len <= N; ++len)
		{
			for (int l = 0; l + len <= N; ++l)
			{
				int r = l + len;
				if (s[l] == s[r-1] && dp[l+1][r-1])
					dp[l][r] = true;
			}
		}

		int res = 0;
		for (int i = 0; i < N; ++i)
			for (int j = i+1; j <= N; ++j)
				res += dp[i][j];
		return res;
	};

	int res = calc();
	for (int i = 0; i < N; ++i)
	{
		char tmp = s[i];
		for (char c = 'a'; c <= 'z'; ++c)
		{	
			s[i] = c;
			res = max(res, calc());
		}
		s[i] = tmp;
	}
	return res;
}


int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> s;
	N = strlen(s);

	// for (int i = 0; i < N; ++i)
	// 	for (int j = 0; j < N; ++j)
	// 		dp[i][j][0] = dp[i][j][1] = {-1, -1};

	cout << solve() << '\n';
	return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 37
• Subtask 3: 0 / 46