Submission #738459

#	Time	Username	Problem	Language	Result	Execution time	Memory
738459		Abrar_Al_Samit	Palindromes (APIO14_palindrome)	C++17	23 / 100	1062 ms	1628 KiB

palindrome

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

const int mod = 1e9 + 9;
const int b = 31;
const int nax = 10003;

map<long long,int>cnt;
string s;
long long p[nax];
int n;
long long pwr[nax];
long long ans = 0;

long long get(int l, int r) {
	long long ret = p[r];
	if(l) ret -= p[l-1];

	ret *= pwr[n-r-1];
	ret %= mod;
	if(ret < 0) ret += mod;
	return ret;
}
void PlayGround() {
	cin>>s;
	n = s.size();

	long long pw = 1;
	for(int i=0; i<n; ++i) {
		pwr[i] = pw;
		p[i] = (pw * (s[i]-'a'+1));
		if(i) p[i] += p[i-1];

		p[i] %= mod;
		pw = (pw * b) % mod;
	}


	for(int i=0; i<n; ++i) {
		for(int j=0;  ; ++j) {
			if(i-j<0 || i+j>=n) break;
			if(s[i-j]!=s[i+j]) break;

			long long h_val = get(i-j, i+j);
			cnt[h_val]++;
			ans = max(ans, (j*2+1) * 1LL * cnt[h_val]);
		}
	}

	for(int i=0; i<n-1; ++i) {
		for(int j=0; ; ++j) {
			if(i-j<0 || i+j+1>=n) break;
			if(s[i-j]!=s[i+j+1]) break;

			long long h_val = get(i-j, i+j+1);
			cnt[h_val]++;
			ans = max(ans, (j+1)*2LL * cnt[h_val]);
		}
	}
	cout<<ans<<'\n';

	// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	PlayGround();
	return 0;
}

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