oj.uz

Submission #511572

# Submission time Handle Problem Language Result Execution time Memory
511572 2022-01-16T02:32:40 Z Monarchuwu Palindromic Partitions (CEOI17_palindromic) C++17
60 / 100
 10000 ms 22052 KB 
#include<iostream>
#include<algorithm>
#include<string>
#include<bitset>
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

const int N = 1e6 + 16, mod = 1e9 + 7, base = 331;
const ll mod2 = (ll)mod * mod;
int n;
string s;
ll pw[N], hsh[N];
ll get(int l, int r) {
    return (hsh[r] - hsh[l - 1] * pw[r - l + 1] + mod2) % mod;
}

int dp[N];
int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    pw[0] = 1;
    for (int i = 1; i < N; ++i)
        pw[i] = pw[i - 1] * base % mod;

    int test; cin >> test; while (test--) {
        cin >> s; n = s.size();
        s = " " + s;

        for (int i = 1; i <= n; ++i)
            hsh[i] = (hsh[i - 1] * base + s[i]) % mod;

        fill(dp + 1, dp + n + 1, -N);
        for (int i = 1; i <= n / 2; ++i)
            for (int j = 1; j <= i; ++j)
                if (get(j, i) == get(n - i + 1, n - j + 1))
                    dp[i] = max(dp[i], dp[j - 1] + 2);

        int ans(1);
        for (int i = 1; i <= n / 2; ++i) {
            ans = max(ans, dp[i] + (i * 2 == n ? 0 : 1));
        }
        cout << ans << '\n';
    }
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/
/*
==================================================+
INPUT:                                            |
--------------------------------------------------|
4
bonobo
deleted
racecar
racecars
--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|
3
5
7
1
--------------------------------------------------|
==================================================+
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8144 KB Output is correct
2 Correct 8 ms 8128 KB Output is correct
3 Correct 7 ms 8144 KB Output is correct
4 Correct 8 ms 8144 KB Output is correct
5 Correct 7 ms 8028 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8144 KB Output is correct
2 Correct 8 ms 8128 KB Output is correct
3 Correct 7 ms 8144 KB Output is correct
4 Correct 8 ms 8144 KB Output is correct
5 Correct 7 ms 8028 KB Output is correct
6 Correct 9 ms 8092 KB Output is correct
7 Correct 8 ms 8140 KB Output is correct
8 Correct 8 ms 8140 KB Output is correct
9 Correct 8 ms 8140 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8144 KB Output is correct
2 Correct 8 ms 8128 KB Output is correct
3 Correct 7 ms 8144 KB Output is correct
4 Correct 8 ms 8144 KB Output is correct
5 Correct 7 ms 8028 KB Output is correct
6 Correct 9 ms 8092 KB Output is correct
7 Correct 8 ms 8140 KB Output is correct
8 Correct 8 ms 8140 KB Output is correct
9 Correct 8 ms 8140 KB Output is correct
10 Correct 509 ms 8396 KB Output is correct
11 Correct 228 ms 8344 KB Output is correct
12 Correct 428 ms 8384 KB Output is correct
13 Correct 300 ms 8340 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8144 KB Output is correct
2 Correct 8 ms 8128 KB Output is correct
3 Correct 7 ms 8144 KB Output is correct
4 Correct 8 ms 8144 KB Output is correct
5 Correct 7 ms 8028 KB Output is correct
6 Correct 9 ms 8092 KB Output is correct
7 Correct 8 ms 8140 KB Output is correct
8 Correct 8 ms 8140 KB Output is correct
9 Correct 8 ms 8140 KB Output is correct
10 Correct 509 ms 8396 KB Output is correct
11 Correct 228 ms 8344 KB Output is correct
12 Correct 428 ms 8384 KB Output is correct
13 Correct 300 ms 8340 KB Output is correct
14 Execution timed out 10020 ms 22052 KB Time limit exceeded
15 Halted 0 ms 0 KB -