Submission #42054

#	Time	Username	Problem	Language	Result	Execution time	Memory
42054		fest	Palindromes (APIO14_palindrome)	C++14	0 / 100	1085 ms	1388 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], odd[N], even[N], nex_odd[N], nex_even[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};
}

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];
	}
	int ro = 0, re = 0;
	ll ans = 0;
	odd[ro++] = 1;
	cnt[get(1, 1)]++;
	ans = 1;
	for (int i = 2; i <= n; i++) {
		int nro = 0, nre = 0;
		for (int j = 0; j < ro; j++) {
			int p = odd[j];
			if (p - (i - p) < 1) continue;
			if (s[p - (i - p) - 1] != s[i - 1]) continue;
			nex_odd[nro++] = p;
			cnt[get(p - (i - p), i)]++;
			ans = max(ans, cnt[get(p - (i - p), i)] * 1ll * ((i - p) * 2 + 1));
		}
		for (int j = 0; j < re; j++) {
			int p = even[j];
			if (p - (i - p + 1) < 1) continue;
			if (s[p - (i - p + 1) - 1] != s[i - 1]) continue;
			nex_even[nre++] = p;
			cnt[get(p - (i - p + 1), i)]++;
			ans = max(ans, cnt[get(p - (i - p + 1), i)] * 1ll * (i - p + 1) * 2ll);
		}
		nex_odd[nro++] = i;
		if (s[i - 1] == s[i - 2]) {
			nex_even[nre++] = i;
			cnt[get(i - 1, i)]++;
			ans = max(ans, cnt[get(i - 1, i)] * 2ll);
		}
		swap(nex_odd, odd);
		swap(nro, ro);
		swap(nex_even, even);
		swap(nre, re);
	}
	cout << ans;
	return 0;	
}

Compilation message (stderr)

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

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