Submission #972088

#	Time	Username	Problem	Language	Result	Execution time	Memory
972088		MuhammadSaram	Palindromes (APIO14_palindrome)	C++17	23 / 100	77 ms	131072 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int h=71, mod = 1e9 + 7;

signed main()
{
	string s;
	cin>>s;
	int n=s.size();
	int ha[n][n];
	bool dp[n][n];
	int ans=0;
	int cn[26]={},ct[26]={};
	for (int i=0;i<n;i++)
	{
		int x=0;
		for (int j=i;j<n;j++)
		{
			x*=h,x+=s[j],x%=mod;
			ha[i][j]=x;
		}
		dp[i][i]=1;
		ans=max(ans,++cn[s[i]-'a']);
		if (i)
			dp[i-1][i]=(s[i-1]==s[i]);
		if (i and dp[i-1][i])
			ans=max(ans,(++ct[s[i-1]-'a'])*2);
	}
	for (int len=2;len<n;len++)
	{
		unordered_map<int,int> cnt;
		for (int i=0;i+len<n;i++)
		{
			int j=i+len;
			dp[i][j]=dp[i+1][j-1]&(s[i]==s[j]);
			if (dp[i][j])
				ans=max(ans,(len+1)*(++cnt[ha[i][j]]));
		}
	}
	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