Submission #143798

#	Time	Username	Problem	Language	Result	Execution time	Memory
143798		MB81	Palindromic Partitions (CEOI17_palindromic)	C++11	60 / 100	2019 ms	3988 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
typedef pair<int,int> pii;
typedef pair<int64,int64> pii64;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define sz(x) (x).size()
#define all(x) (x).begin(), (x).end()

const int maxn = 1e4+10;
const int base = 101;
const int64 MO = 1e9+7;
const int64 IN = 1e9;

int pw[maxn];
int h1[maxn];
int dp[maxn];
int T;

int geth (int l, int r) {
	if (l == 0)
		return h1[r];
	int res = h1[r];
	res = (res - 1LL * h1[l - 1] * pw[r - l + 1] % MO) % MO;
	res = (res + MO) % MO;
	return res;
}

int main () {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	// pw
	pw[0] = 1;
	for (int i = 1; i < maxn; i++)
		pw[i] = 1LL * pw[i - 1] * base % MO;
	//
	cin >> T;
while (T--) {
	string s;
	cin >> s;
	// h1
	h1[0] = s[0] - 'a' + 1;
	for (int i = 1; i < sz(s); i++)
		h1[i] = (1LL * h1[i - 1] * base % MO + s[i] - 'a' + 1) % MO;
	// dp
	fill(dp, dp + maxn, -IN);
	for (int i = 0; i < sz(s) / 2; i++) {
		if (h1[i] == geth(sz(s) - i - 1, sz(s) - 1))
			dp[i] = 1;
		for (int t = 0; t < i; t++)
			if (geth(i - t, i) == geth(sz(s) - i - 1, sz(s) - i - 1 + t))
				dp[i] = max(dp[i], dp[i - t - 1] + 1);
	}
	// ans
	if (sz(s) % 2) {
		int ans = 0;
		for (int i = 0; i < sz(s) / 2; i++)
			ans = max(ans, dp[i]);
		cout << ans * 2 + 1 << "\n";
	} else {
		int ans = 1;
		ans = max(ans, dp[sz(s) / 2 - 1] * 2);
		for (int i = 0; i < sz(s) / 2 - 1; i++)
			ans = max(ans, dp[i] * 2 + 1);
		cout << ans << "\n";
	}
}
}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < sz(s); i++)
                    ^
palindromic.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < sz(s) / 2; i++) {
                  ~~^~~~~~~~~~~
palindromic.cpp:60:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < sz(s) / 2; i++)
                   ~~^~~~~~~~~~~
palindromic.cpp:66:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < sz(s) / 2 - 1; i++)
                   ~~^~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40