Submission #972084

#	Time	Username	Problem	Language	Result	Execution time	Memory
972084		MuhammadSaram	Palindromes (APIO14_palindrome)	C++17	23 / 100	1066 ms	10232 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int h=71, mod = 1e9 + 7;
const int h1=53, mod1 = 1e9 + 9;
const int M = 3e5 + 1;

int pre[M],pre1[M],suf[M],suf1[M];

int power(int a,int b,int md)
{
	int ans=1;
	int x=a;
	while (b)
	{
		if (b&1)
			ans*=x;
		ans%=md;
		x*=x;
		x%=md;
		b>>=1;
	}
	return ans;
}

int sub(int a,int b,int md)
{
	int ans=a%md-b%md;
	return (ans+md)%md;
}

bool pal(int l,int r)
{
	bool b=sub(pre[r],pre[l]*power(h,r-l,mod),mod)==sub(suf[l],suf[r]*power(h,r-l,mod),mod);
	bool b1=sub(pre1[r],pre1[l]*power(h1,r-l,mod1),mod1)==sub(suf1[l],suf1[r]*power(h1,r-l,mod1),mod1);
	return b and b1;
}

pair<int,int> ha(int l,int r)
{
	return {sub(pre[r],pre[l]*power(h,r-l,mod),mod),sub(pre1[r],pre1[l]*power(h1,r-l,mod1),mod1)};
}

signed main()
{
	string s;
	cin>>s;
	int n=s.size();
	for (int i=0;i<n;i++)
	{
		pre[i+1]=pre[i]*h+s[i],pre1[i+1]=pre1[i]*h1+s[i];
		pre[i+1]%=mod,pre1[i+1]%=mod1;
	}
	for (int i=n-1;i>=0;i--)
	{
		suf[i]=suf[i+1]*h+s[i],suf1[i]=suf1[i+1]*h1+s[i];
		suf[i]%=mod,suf1[i]%=mod1;
	}
	int ans=0;
	for (int len=1;len<=n;len++)
	{
		map<pair<int,int>,int> cnt;
		int x=0;
		for (int i=0;i+len<=n;i++)
			if (pal(i,i+len))
				x=max(x,++cnt[ha(i,i+len)]);
		ans=max(ans,x*len);
	}
	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