oj.uz

답안 #859023

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -