oj.uz

Submission #339703

# Submission time Handle Problem Language Result Execution time Memory
339703 2020-12-26T01:34:55 Z nandonathaniel Palindromic Partitions (CEOI17_palindromic) C++14
60 / 100
 920 ms 5000 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=10005,MOD=1e9+7;
 
int pref[MAXN],pkt[MAXN];
map<int,int> dp[MAXN];
string s;
 
int get(int L,int R){
	if(L>R)return 0;
	return (pref[R]-((1LL*pref[L-1]*pkt[R-L+1])%MOD)+MOD)%MOD;
}

int DP(int L,int R){
	if(L>R)return 0;
	if(dp[L].count(R))return dp[L][R];
	int ret=1;
	for(int i=(R-L+1)/2;i>=1;i--){
		if(get(L,L+i-1)==get(R-i+1,R)){
			ret=max(ret,2+DP(L+i,R-i));
		}
	}
	return dp[L][R]=ret;
}
 
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t,n;
	cin >> t;
	while(t--){
		cin >> s;
		n=(int)s.length();
		for(int i=1;i<=n;i++)dp[i].clear();
		pkt[0]=1;
		for(int i=0;i<n;i++){
			pref[i+1]=(26LL*pref[i]+s[i]-'a')%MOD;
			pkt[i+1]=(26LL*pkt[i])%MOD;
		}
		cout << DP(1,n) << '\n';
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 896 KB Output is correct
5 Correct 1 ms 748 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 896 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 2 ms 876 KB Output is correct
8 Correct 1 ms 888 KB Output is correct
9 Correct 2 ms 896 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 896 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 2 ms 876 KB Output is correct
8 Correct 1 ms 888 KB Output is correct
9 Correct 2 ms 896 KB Output is correct
10 Correct 920 ms 1828 KB Output is correct
11 Correct 125 ms 1132 KB Output is correct
12 Correct 20 ms 1004 KB Output is correct
13 Correct 603 ms 1004 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 896 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 2 ms 876 KB Output is correct
8 Correct 1 ms 888 KB Output is correct
9 Correct 2 ms 896 KB Output is correct
10 Correct 920 ms 1828 KB Output is correct
11 Correct 125 ms 1132 KB Output is correct
12 Correct 20 ms 1004 KB Output is correct
13 Correct 603 ms 1004 KB Output is correct
14 Runtime error 7 ms 5000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -