oj.uz

Submission #132741

# Submission time Handle Problem Language Result Execution time Memory
132741 2019-07-19T12:45:04 Z Bench0310 Palindromic Partitions (CEOI17_palindromic) C++17
60 / 100
 10000 ms 53464 KB 
#include <bits/stdc++.h>

using namespace std;
const int N=1000000;
const long long p=29;
const long long mod=1000000007;

long long e[N];
int n;
string s;
int dp[N];

int solve(int l,int r)
{
    if(l>r) return 0;
    if(l==r) return 1;
    if(dp[l]!=-1) return dp[l];
    int res=0;
    long long one=0,two=0;
    for(int i=0;l+i<r-i;i++)
    {
        one=((one*p)+(s[l+i]-'a'))%mod;
        two=(two+e[i]*(s[r-i]-'a'))%mod;
        if(one==two) res=max(res,2+solve(l+i+1,r-i-1));
    }
    if(res==0) res=1;
    return dp[l]=res;
}

int main()
{
    e[0]=1;
    for(int i=1;i<N;i++) e[i]=(e[i-1]*p)%mod;
    int t;
    cin >> t;
    while(t--)
    {
        cin >> s;
        n=s.size();
        memset(dp,-1,sizeof dp);
        cout << solve(0,n-1) << endl;
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12024 KB Output is correct
2 Correct 19 ms 12024 KB Output is correct
3 Correct 18 ms 12024 KB Output is correct
4 Correct 19 ms 12024 KB Output is correct
5 Correct 19 ms 12024 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12024 KB Output is correct
2 Correct 19 ms 12024 KB Output is correct
3 Correct 18 ms 12024 KB Output is correct
4 Correct 19 ms 12024 KB Output is correct
5 Correct 19 ms 12024 KB Output is correct
6 Correct 19 ms 12024 KB Output is correct
7 Correct 19 ms 12024 KB Output is correct
8 Correct 19 ms 12016 KB Output is correct
9 Correct 20 ms 12024 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12024 KB Output is correct
2 Correct 19 ms 12024 KB Output is correct
3 Correct 18 ms 12024 KB Output is correct
4 Correct 19 ms 12024 KB Output is correct
5 Correct 19 ms 12024 KB Output is correct
6 Correct 19 ms 12024 KB Output is correct
7 Correct 19 ms 12024 KB Output is correct
8 Correct 19 ms 12016 KB Output is correct
9 Correct 20 ms 12024 KB Output is correct
10 Correct 414 ms 12664 KB Output is correct
11 Correct 83 ms 12280 KB Output is correct
12 Correct 35 ms 12152 KB Output is correct
13 Correct 342 ms 12332 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12024 KB Output is correct
2 Correct 19 ms 12024 KB Output is correct
3 Correct 18 ms 12024 KB Output is correct
4 Correct 19 ms 12024 KB Output is correct
5 Correct 19 ms 12024 KB Output is correct
6 Correct 19 ms 12024 KB Output is correct
7 Correct 19 ms 12024 KB Output is correct
8 Correct 19 ms 12016 KB Output is correct
9 Correct 20 ms 12024 KB Output is correct
10 Correct 414 ms 12664 KB Output is correct
11 Correct 83 ms 12280 KB Output is correct
12 Correct 35 ms 12152 KB Output is correct
13 Correct 342 ms 12332 KB Output is correct
14 Execution timed out 10086 ms 53464 KB Time limit exceeded
15 Halted 0 ms 0 KB -