Submission #42063

#	Time	Username	Problem	Language	Result	Execution time	Memory
42063		fest	Palindromes (APIO14_palindrome)	C++14	23 / 100	1081 ms	1456 KiB

palindrome

// fest
#include <bits/stdc++.h>	

#define pb push_back
#define F first
#define S second
#define y1 dasdasfasfas
#define x1 wqdadfasfasfas
#define All(c) c.begin(), c.end()
#define SZ(A) (int((A).size()))
#define umap unordered_map
#define FILENAME ""
#define __ fflush(stdout)

typedef long long ll;
typedef long double ld;    

using namespace std;

void FREOPEN() {
	#ifdef COMP
		freopen(".in", "r", stdin);
		freopen("2.out", "w", stdout);
	#endif
}                           

inline double Time() {return (clock() * 1.0) / CLOCKS_PER_SEC; }             

const int N = 10500, M = 2, inf = 1e9 * 2, MOD = (int)1e9 + 7;

char CH[N];

const ll INF = 1e18;

const int dx[] = {1, -1, 0, 0, -1, 1, -1, 1};
const int dy[] = {0, 0, 1, -1, -1, 1, 1, -1};
const int P[] = {2019, 2017};
const int mod[] = {(int)1e9 + 3, (int)1e9 + 9};

map<pair<int, int>, int> cnt;

int h[M][N], pr[M][N];

int n;

pair<int, int> get(int l, int r) {
	int f = ((h[0][r] - h[0][l - 1] + mod[0]) * 1ll * pr[0][n - l]) % mod[0];
	int s = ((h[1][r] - h[1][l - 1] + mod[1]) * 1ll * pr[1][n - l]) % mod[1];
	return {f, s};
}

void relax(ll &ans, int l, int r) {
	cnt[get(l, r)]++;
	ans = max(ans, cnt[get(l, r)] * 1ll * (r - l + 1));
}

int main() {
  
	FREOPEN();
	scanf("%s", CH);
	string s = CH;
	n = SZ(s);
	for (int j = 0; j < M; j++) {
		pr[j][0] = 1;
		for (int i = 1; i <= n; i++) pr[j][i] = (pr[j][i - 1] * 1ll * P[j]) % mod[j];
		for (int i = 1; i <= n; i++) h[j][i] = (h[j][i - 1] + (s[i - 1] * 1ll * pr[j][i])) % mod[j];
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		int sz = 1;
		relax(ans, i, i);
		while (i - sz >= 1 && i + sz <= n && s[i - sz - 1] == s[i + sz - 1]) {
			relax(ans, i - sz, i + sz);
			sz++;	
		}
		sz = 1;
		if (i == 1 || s[i - 1] != s[i - 2]) continue;
		relax(ans, i - 1, i);
		while (i - sz - 1 >= 1 && i + sz <= n && s[i - sz - 2] == s[i + sz - 1]) {
			relax(ans, i - sz - 1, i + sz);
			sz++;
		}
	}
	cout << ans;
	return 0;	
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:60:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", CH);
                 ^

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