Submission #703231

#	Time	Username	Problem	Language	Result	Execution time	Memory
703231		600Mihnea	Palindromes (APIO14_palindrome)	C++17	23 / 100	711 ms	131072 KiB

palindrome

#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>

using namespace std;

int dumb(string s)
{
	int n = (int)s.size();
	vector<vector<int>> lcp(n, vector<int>(n, 0));
	vector<vector<bool>> ispal(n, vector<bool>(n, 0));

	for (int i = 0; i < n; i++)
	{
		lcp[i][i] = n - i;
	}
	for (int i = n - 1; i >= 0; i--)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (s[i] == s[j])
			{
				int c = 0;
				if (i + 1 < n && j + 1 < n)
				{
					c += lcp[i + 1][j + 1];
				}
				lcp[i][j] = lcp[j][i] = 1 + c;
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		ispal[i][i] = 1;
	}
	for (int i = 0; i + 1 < n; i++)
	{
		ispal[i][i + 1] = (s[i] == s[i + 1]);
	}
	for (int len = 3; len <= n; len++)
	{
		for (int i = 0; i + len - 1 < n; i++)
		{
			int j = i + len - 1;
			ispal[i][j] = ispal[i + 1][j - 1] & (s[i] == s[j]);
		}
	}
	int sol = 0;
	for (int len = 1; len <= n; len++)
	{
		for (int i = 0; i + len - 1 < n; i++)
		{
			int j = i + len - 1;
			if (ispal[i][j])
			{
				int matches = 0;
				for (int k = 0; k < n; k++)
				{
					matches += (lcp[k][i] >= len);
				}
				sol = max(sol, len * matches);
			}
		}
	}
	return sol;
}

signed main()
{
#ifdef ONPC	
	FILE* stream;
	freopen_s(&stream, "input.txt", "r", stdin);
#else
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
	
	string s;
	cin >> s;
	cout << dumb(s) << "\n";


	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27