oj.uz

답안 #339703

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

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

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

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

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