oj.uz

Submission #858988

# Submission time Handle Problem Language Result Execution time Memory
858988 2023-10-09T14:08:01 Z VinhLuu Palindromic Partitions (CEOI17_palindromic) C++17
60 / 100
 10000 ms 71956 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;
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;
    //cout << l << " " << r << "\n";
  	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 ++){
       // cout << l << " " << l + j - 1 << " " << r - j + 1 << " " << r << "u\n";
        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 = 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;
    cout << dfs(1) << "\n";
}
 
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    lt[0] = 1;
    for(int i = 1; i <= Max - 5; i ++) lt[i] = (1LL * lt[i-1] * 26)%mod;
    int tt; cin >> tt;
    while(tt--) solve();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10588 KB Output is correct
2 Correct 7 ms 10708 KB Output is correct
3 Correct 6 ms 10588 KB Output is correct
4 Correct 6 ms 10588 KB Output is correct
5 Correct 6 ms 10588 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10588 KB Output is correct
2 Correct 7 ms 10708 KB Output is correct
3 Correct 6 ms 10588 KB Output is correct
4 Correct 6 ms 10588 KB Output is correct
5 Correct 6 ms 10588 KB Output is correct
6 Correct 7 ms 10588 KB Output is correct
7 Correct 6 ms 10712 KB Output is correct
8 Correct 6 ms 10588 KB Output is correct
9 Correct 7 ms 10588 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10588 KB Output is correct
2 Correct 7 ms 10708 KB Output is correct
3 Correct 6 ms 10588 KB Output is correct
4 Correct 6 ms 10588 KB Output is correct
5 Correct 6 ms 10588 KB Output is correct
6 Correct 7 ms 10588 KB Output is correct
7 Correct 6 ms 10712 KB Output is correct
8 Correct 6 ms 10588 KB Output is correct
9 Correct 7 ms 10588 KB Output is correct
10 Correct 343 ms 11276 KB Output is correct
11 Correct 62 ms 10840 KB Output is correct
12 Correct 15 ms 10844 KB Output is correct
13 Correct 276 ms 10976 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10588 KB Output is correct
2 Correct 7 ms 10708 KB Output is correct
3 Correct 6 ms 10588 KB Output is correct
4 Correct 6 ms 10588 KB Output is correct
5 Correct 6 ms 10588 KB Output is correct
6 Correct 7 ms 10588 KB Output is correct
7 Correct 6 ms 10712 KB Output is correct
8 Correct 6 ms 10588 KB Output is correct
9 Correct 7 ms 10588 KB Output is correct
10 Correct 343 ms 11276 KB Output is correct
11 Correct 62 ms 10840 KB Output is correct
12 Correct 15 ms 10844 KB Output is correct
13 Correct 276 ms 10976 KB Output is correct
14 Execution timed out 10093 ms 71956 KB Time limit exceeded
15 Halted 0 ms 0 KB -