Submission #738485

#	Time	Username	Problem	Language	Result	Execution time	Memory
738485		Abrar_Al_Samit	Palindromes (APIO14_palindrome)	C++17	47 / 100	344 ms	2524 KiB

palindrome

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

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

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

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) {
		bool ok1 = 1, ok2 = 1;
		for(int j=0, len=1;  ; ++j, len+=2) {
			if(i-j<0 || i+j>=n) break;
			if(s[i-j]!=s[i+j]) {
				ok1 = 0;
			}
			if(i+j+1>=n) ok2 = 0;
			if(ok2 && s[i-j]!=s[i+j+1]) {
				ok2 = 0;
			}

			if(!ok1 && !ok2) break;

			if(ok1) {
				long long h_val = p[i+j];
				if(i-j) h_val -= p[i-j-1];
				h_val *= pwr[n-1-(i+j)];
				h_val %= mod;
				if(h_val<0) h_val += mod;

				long long app = ++cnt[len][h_val];
				ans = max(ans, len * app);
			}
			if(ok2) {
				long long h_val = p[i+j+1];
				if(i-j) h_val -= p[i-j-1];
				h_val *= pwr[n-1-(i+j+1)];
				h_val %= mod;
				if(h_val<0) h_val += mod;

				long long app = ++cnt[len+1][h_val];
				ans = max(ans, (1+len) * app);
			}
		}
	}
	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: 24 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27