oj.uz

Submission #859016

# Submission time Handle Problem Language Result Execution time Memory
859016 2023-10-09T14:22:50 Z VinhLuu Palindromic Partitions (CEOI17_palindromic) C++17
60 / 100
 10000 ms 91416 KB 
#pragma GCC optimize("O3")
#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(){
    cin >> s;
    n = s.size();
    s = " " + s;
    for(int i = 1; i <= n; i ++) dp[i] = 0;
    for(int i = 1; i <= n; i ++) hs[i] = ((1LL * hs[i - 1] * 26)%mod + (int)(s[i] - 'a'))%mod;
    for(int i = 1; i <= n; i ++) t[i] = ((1LL * t[i - 1] * 26)%dm + (int)(s[i] - 'a'))%dm;
    cout << dfs(1) << "\n";
}
 
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    lt[0] = 1;
    pw[0] = 1;
    for(int i = 1; i <= Max - 5; i ++) lt[i] = (1LL * lt[i-1] * 26)%mod, pw[i] = (1LL * pw[i - 1] * 26)%dm;
    int tt; cin >> tt;
    while(tt--) solve();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19048 KB Output is correct
2 Correct 7 ms 19036 KB Output is correct
3 Correct 7 ms 19036 KB Output is correct
4 Correct 7 ms 19032 KB Output is correct
5 Correct 8 ms 19036 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19048 KB Output is correct
2 Correct 7 ms 19036 KB Output is correct
3 Correct 7 ms 19036 KB Output is correct
4 Correct 7 ms 19032 KB Output is correct
5 Correct 8 ms 19036 KB Output is correct
6 Correct 8 ms 19036 KB Output is correct
7 Correct 7 ms 19096 KB Output is correct
8 Correct 7 ms 19036 KB Output is correct
9 Correct 8 ms 19036 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19048 KB Output is correct
2 Correct 7 ms 19036 KB Output is correct
3 Correct 7 ms 19036 KB Output is correct
4 Correct 7 ms 19032 KB Output is correct
5 Correct 8 ms 19036 KB Output is correct
6 Correct 8 ms 19036 KB Output is correct
7 Correct 7 ms 19096 KB Output is correct
8 Correct 7 ms 19036 KB Output is correct
9 Correct 8 ms 19036 KB Output is correct
10 Correct 531 ms 19992 KB Output is correct
11 Correct 68 ms 19288 KB Output is correct
12 Correct 17 ms 19032 KB Output is correct
13 Correct 288 ms 19356 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 19048 KB Output is correct
2 Correct 7 ms 19036 KB Output is correct
3 Correct 7 ms 19036 KB Output is correct
4 Correct 7 ms 19032 KB Output is correct
5 Correct 8 ms 19036 KB Output is correct
6 Correct 8 ms 19036 KB Output is correct
7 Correct 7 ms 19096 KB Output is correct
8 Correct 7 ms 19036 KB Output is correct
9 Correct 8 ms 19036 KB Output is correct
10 Correct 531 ms 19992 KB Output is correct
11 Correct 68 ms 19288 KB Output is correct
12 Correct 17 ms 19032 KB Output is correct
13 Correct 288 ms 19356 KB Output is correct
14 Execution timed out 10070 ms 91416 KB Time limit exceeded
15 Halted 0 ms 0 KB -