oj.uz

Submission #927934

# Submission time Handle Problem Language Result Execution time Memory
927934 2024-02-15T14:11:39 Z TAhmed33 Palindromic Partitions (CEOI17_palindromic) C++
100 / 100
 355 ms 66004 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;
const int base = 9973;
int add (int a, int b) {
	return (MOD + (a + b) % MOD) % MOD;
}
int sub (int a, int b) {
	return ((a - b) % MOD + MOD) % MOD;
}
int mul (int a, int b) {
	return (a * b) % MOD;
}
int n;
string s;
int pw[1000001];
int p_hash[1000001];
int dp[1000001];
inline int get (int l, int r) {
	return sub(p_hash[r + 1], mul(p_hash[l], pw[r - l + 1]));
}
int ans (int l, int r) {
	if (l == r) {
		return 1;
	}
	if (l > r) {
		return 0;
	}
	int &ret = dp[l];
	if (ret != -1) return ret;
	ret = 1;
	for (int i = l; i < n/2; i++) {
		int x = i - l + 1;
		if (get(l, i) == get(r - x + 1, r)) {
			ret = ans(i + 1, r - x) + 2	;
			break;
		}
	}
	return ret;
}
void solve () {
	cin >> s; n = s.length();
	for (int i = 1; i <= n; i++) {
		dp[i - 1] = -1;
		p_hash[i] = add(mul(p_hash[i - 1], base), s[i - 1]);
	}
	cout << ans(0, n - 1) << '\n';
}
signed main () {
	pw[0] = 1;
	for (int i = 1; i <= 1e6; i++) {
		pw[i] = mul(base, pw[i - 1]);
	}
	int t;
	cin >> t;
	while (t--) solve();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9308 KB Output is correct
2 Correct 8 ms 9308 KB Output is correct
3 Correct 8 ms 9308 KB Output is correct
4 Correct 8 ms 9308 KB Output is correct
5 Correct 8 ms 9156 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9308 KB Output is correct
2 Correct 8 ms 9308 KB Output is correct
3 Correct 8 ms 9308 KB Output is correct
4 Correct 8 ms 9308 KB Output is correct
5 Correct 8 ms 9156 KB Output is correct
6 Correct 8 ms 9308 KB Output is correct
7 Correct 8 ms 9308 KB Output is correct
8 Correct 8 ms 9308 KB Output is correct
9 Correct 8 ms 9304 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9308 KB Output is correct
2 Correct 8 ms 9308 KB Output is correct
3 Correct 8 ms 9308 KB Output is correct
4 Correct 8 ms 9308 KB Output is correct
5 Correct 8 ms 9156 KB Output is correct
6 Correct 8 ms 9308 KB Output is correct
7 Correct 8 ms 9308 KB Output is correct
8 Correct 8 ms 9308 KB Output is correct
9 Correct 8 ms 9304 KB Output is correct
10 Correct 12 ms 9820 KB Output is correct
11 Correct 10 ms 9564 KB Output is correct
12 Correct 11 ms 9564 KB Output is correct
13 Correct 11 ms 9564 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9308 KB Output is correct
2 Correct 8 ms 9308 KB Output is correct
3 Correct 8 ms 9308 KB Output is correct
4 Correct 8 ms 9308 KB Output is correct
5 Correct 8 ms 9156 KB Output is correct
6 Correct 8 ms 9308 KB Output is correct
7 Correct 8 ms 9308 KB Output is correct
8 Correct 8 ms 9308 KB Output is correct
9 Correct 8 ms 9304 KB Output is correct
10 Correct 12 ms 9820 KB Output is correct
11 Correct 10 ms 9564 KB Output is correct
12 Correct 11 ms 9564 KB Output is correct
13 Correct 11 ms 9564 KB Output is correct
14 Correct 355 ms 66004 KB Output is correct
15 Correct 188 ms 50084 KB Output is correct
16 Correct 289 ms 34296 KB Output is correct
17 Correct 184 ms 32520 KB Output is correct