제출 #997364

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
997364		vjudge1	회문 (APIO14_palindrome)	C++17	23 / 100	1072 ms	13680 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main()
{
	string s;
	cin>>s;
	int n=s.size();
	vector<int> ind[n];
	bool vis1[n]={};
	int ans=0;
	for (int i=0;i<n;i++)
	{
		if (vis1[i])
			continue;
		for (int j=i;j<n;j++)
			if (s[i]==s[j])
				ind[i].push_back(j),vis1[j]=true;
		ans=max(ans,(int)ind[i].size());
	}
	for (int sz=1;sz<n;sz++)
	{
		bool vis[n]={};
		for (int i=0;i<n;i++)
		{
			if (vis[i] or ind[i].empty())
				continue;
			vector<int> ind1[26];
			for (int j:ind[i])
			{
				vis[j]=true;
				if (j<sz or j+sz>=n or s[j-sz]!=s[j+sz])
					continue;
				ind1[s[j-sz]-'a'].push_back(j);
			}
			vector<int> v;
			for (int j:ind[i])
			{
				if (j<sz or j+sz>=n or s[j-sz]!=s[j+sz])
					continue;
				if (ind1[s[j-sz]-'a'][0]==i)
					v=ind1[s[j-sz]-'a'];
				else
					ind[ind1[s[j-sz]-'a'][0]]=ind1[s[j-sz]-'a'];
			}
			ind[i]=v;
		}
		for (int i=0;i<n;i++)
			ans=max(ans,(sz*2+1)*(int)ind[i].size());
	}
	for (int i=0;i<n;i++)
		vis1[i]=0,ind[i].clear();
	for (int i=0;i<n-1;i++)
	{
		if (vis1[i] or s[i]!=s[i+1])
			continue;
		for (int j=i;j<n-1;j++)
			if (s[i]==s[j] and s[j]==s[j+1])
				ind[i].push_back(j),vis1[j]=true;
		ans=max(ans,(int)ind[i].size()*2);
	}
	for (int sz=1;sz<n;sz++)
	{
		bool vis[n]={};
		for (int i=0;i<n;i++)
		{
			if (vis[i] or ind[i].empty())
				continue;
			vector<int> ind1[26];
			for (int j:ind[i])
			{
				vis[j]=true;
				if (j<sz or j+sz+1>=n or s[j-sz]!=s[j+sz+1])
					continue;
				ind1[s[j-sz]-'a'].push_back(j);
			}
			vector<int> v;
			for (int j:ind[i])
			{
				if (j<sz or j+sz+1>=n or s[j-sz]!=s[j+sz+1])
					continue;
				if (ind1[s[j-sz]-'a'][0]==i)
					v=ind1[s[j-sz]-'a'];
				else if(ind1[s[j-sz]-'a'][0]==j)
					ind[j]=ind1[s[j-sz]-'a'];
			}
			ind[i]=v;
		}
		for (int i=0;i<n;i++)
			ans=max(ans,(sz*2+2)*(int)ind[i].size());
	}
	cout<<ans<<endl;

	return 0;
}

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