oj.uz

Submission #143798

# Submission time Handle Problem Language Result Execution time Memory
143798 2019-08-15T07:32:09 Z MB81 Palindromic Partitions (CEOI17_palindromic) C++11
60 / 100
 2019 ms 3988 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 508 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 508 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 4 ms 376 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 508 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 4 ms 376 KB Output is correct
10 Correct 2019 ms 688 KB Output is correct
11 Correct 975 ms 632 KB Output is correct
12 Correct 1806 ms 504 KB Output is correct
13 Correct 1303 ms 600 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 508 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 4 ms 376 KB Output is correct
10 Correct 2019 ms 688 KB Output is correct
11 Correct 975 ms 632 KB Output is correct
12 Correct 1806 ms 504 KB Output is correct
13 Correct 1303 ms 600 KB Output is correct
14 Runtime error 7 ms 3988 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -