oj.uz

Submission #859022

# Submission time Handle Problem Language Result Execution time Memory
859022 2023-10-09T14:29:03 Z VinhLuu Palindromic Partitions (CEOI17_palindromic) C++17
60 / 100
 545 ms 131072 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;
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(string &s){

    n = s.size();
    if(n == 1){
        cout << 1 << "\n";
        return;
    }
    s = " " + s;
    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;
string st[Max];
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> tt;
    mx = 1;
    for(int i = 1; i<= tt; i ++){
        cin >> st[i];
        int o = st[i].size();
        mx = max(mx,o);
    }
    lt[0] = 1;
    pw[0] = 1;
    for(int i = 1; i <= mx; i ++) lt[i] = (1LL * lt[i-1] * 26)%mod, pw[i] = (1LL * pw[i - 1] * 26)%dm;
    for(int i = 1; i<= tt; i ++) solve(st[i]);
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37468 KB Output is correct
2 Correct 10 ms 37504 KB Output is correct
3 Correct 7 ms 37468 KB Output is correct
4 Correct 7 ms 37564 KB Output is correct
5 Correct 7 ms 37564 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37468 KB Output is correct
2 Correct 10 ms 37504 KB Output is correct
3 Correct 7 ms 37468 KB Output is correct
4 Correct 7 ms 37564 KB Output is correct
5 Correct 7 ms 37564 KB Output is correct
6 Correct 7 ms 37468 KB Output is correct
7 Correct 7 ms 37468 KB Output is correct
8 Correct 7 ms 37576 KB Output is correct
9 Correct 8 ms 37724 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37468 KB Output is correct
2 Correct 10 ms 37504 KB Output is correct
3 Correct 7 ms 37468 KB Output is correct
4 Correct 7 ms 37564 KB Output is correct
5 Correct 7 ms 37564 KB Output is correct
6 Correct 7 ms 37468 KB Output is correct
7 Correct 7 ms 37468 KB Output is correct
8 Correct 7 ms 37576 KB Output is correct
9 Correct 8 ms 37724 KB Output is correct
10 Correct 545 ms 40400 KB Output is correct
11 Correct 66 ms 40028 KB Output is correct
12 Correct 17 ms 39772 KB Output is correct
13 Correct 293 ms 40024 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37468 KB Output is correct
2 Correct 10 ms 37504 KB Output is correct
3 Correct 7 ms 37468 KB Output is correct
4 Correct 7 ms 37564 KB Output is correct
5 Correct 7 ms 37564 KB Output is correct
6 Correct 7 ms 37468 KB Output is correct
7 Correct 7 ms 37468 KB Output is correct
8 Correct 7 ms 37576 KB Output is correct
9 Correct 8 ms 37724 KB Output is correct
10 Correct 545 ms 40400 KB Output is correct
11 Correct 66 ms 40028 KB Output is correct
12 Correct 17 ms 39772 KB Output is correct
13 Correct 293 ms 40024 KB Output is correct
14 Runtime error 77 ms 131072 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -