oj.uz

Submission #859026

# Submission time Handle Problem Language Result Execution time Memory
859026 2023-10-09T14:40:07 Z VinhLuu Palindromic Partitions (CEOI17_palindromic) C++17
60 / 100
 10000 ms 68632 KB 
#include <bits/stdc++.h>
#define ll long long
//#define int long long
using namespace std;

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

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

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

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)){
            dp[i] = max(dp[i], 2 + dfs(l + j));
        }
    }
    return dp[i];
}


void solve(){
    cin >> s;
    n = s.size();
    s = " " + s;
    for(int i = ptr; i <= n; i ++) lt[i] = (1LL * lt[i-1] * 26)%mod;
    for(int i = 1; i <= n; i ++) dp[i] = 0, hs[i] = ((1LL * hs[i - 1] * 26)%mod + (int)(s[i] - 'a'))%mod;
    cout << dfs(1) << "\n";
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    lt[0] = 1;
    ptr = 1;
    int tt; cin >> tt;
    while(tt--) solve();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 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 4560 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 4440 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 4560 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 4444 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 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 4560 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 4444 KB Output is correct
10 Correct 390 ms 5208 KB Output is correct
11 Correct 68 ms 4956 KB Output is correct
12 Correct 12 ms 4696 KB Output is correct
13 Correct 321 ms 4884 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 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 4560 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 4444 KB Output is correct
10 Correct 390 ms 5208 KB Output is correct
11 Correct 68 ms 4956 KB Output is correct
12 Correct 12 ms 4696 KB Output is correct
13 Correct 321 ms 4884 KB Output is correct
14 Execution timed out 10016 ms 68632 KB Time limit exceeded
15 Halted 0 ms 0 KB -