oj.uz

Submission #859023

# Submission time Handle Problem Language Result Execution time Memory
859023 2023-10-09T14:30:37 Z VinhLuu Palindromic Partitions (CEOI17_palindromic) C++17
60 / 100
 10000 ms 91412 KB 
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll mod = 1e9 + 7;
const int Max = 1e6 + 5;
const ll dm = 998244353;

string s;
int dp[Max],n, ptr;
ll lt[Max],hs[Max],t[Max],pw[Max];

int get(int i,int j){
    return (hs[j]%mod + mod - (1LL * hs[i - 1]*lt[j - i + 1])%mod)%mod;
}

int got(int i,int j){
    return (t[j]%dm + dm - (1LL * t[i - 1]*pw[j - i + 1])%dm)%dm;
}

int dfs(int i){
    if(dp[i] != 0) return dp[i];
    dp[i] = 1;
    int l = i, r = n - i + 1;
    if(l > r) return dp[i] = 0;
    if(l == r) return dp[i] = 1;
    int mid = (r - l + 1) / 2;
    for(int j = 1; j <= mid; j ++){
        if(get(l, l + j - 1) == get(r - j + 1, r) && got(l, l + j - 1) == got(r - j + 1, r)){
            dp[i] = max(dp[i], 2 + dfs(l + j));
        }
    }
    return dp[i];
}


void solve(){
    cin >> s;
    n = s.size();
    if(n == 1){
        cout << 1 << "\n";
        return;
    }
    s = " " + s;
    for(int i = ptr; i <= n; i ++) lt[i] = (1LL * lt[i-1] * 26)%mod, pw[i] = (1LL * pw[i - 1] * 26)%dm;
    for(int i = 1; i <= n; i ++) {
        dp[i] = 0;
        hs[i] = ((1LL * hs[i - 1] * 26)%mod + (int)(s[i] - 'a'))%mod;
        t[i] = ((1LL * t[i - 1] * 26)%dm + (int)(s[i] - 'a'))%dm;
    }
    cout << dfs(1) << "\n";
}
int tt, mx;
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    lt[0] = 1;
    pw[0] = 1;
    ptr = 1;
    cin >> tt;
    while(tt--) solve();
}

Subtask #1
15.0 / 15.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4456 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4456 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 537 ms 5212 KB Output is correct
11 Correct 64 ms 5108 KB Output is correct
12 Correct 11 ms 4696 KB Output is correct
13 Correct 288 ms 4956 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4456 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 537 ms 5212 KB Output is correct
11 Correct 64 ms 5108 KB Output is correct
12 Correct 11 ms 4696 KB Output is correct
13 Correct 288 ms 4956 KB Output is correct
14 Execution timed out 10095 ms 91412 KB Time limit exceeded
15 Halted 0 ms 0 KB -