oj.uz

Submission #499857

# Submission time Handle Problem Language Result Execution time Memory
499857 2021-12-29T20:10:16 Z pooyashams Palindromic Partitions (CEOI17_palindromic) C++14
60 / 100
 560 ms 49396 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int maxn = 5010;

short dp[maxn];
short mxl[maxn][maxn];
int n;
string s;

inline void fill_mxl()
{
	int mid = n/2;
	for(int i = mid-1; i >= 0; i--)
	{
		for(int j = n-1; j >= mid; j--)
		{
			mxl[i][j-mid] = 0;
			if(s[i] == s[j])
			{
				if(i == mid-1 or j == n-1)
					mxl[i][j-mid] = 1;
				else
					mxl[i][j-mid] = 1+mxl[i+1][j-mid+1];
			}
		}
	}
}

inline void fill_dp()
{
	int mid = n/2;
	if(n & 1)
		dp[mid] = 1;
	else
		dp[mid] = 0;
	for(int i = mid-1; i >= 0; i--)
	{
		dp[i] = 1;
		for(int j = i; j < mid; j++)
		{
			if(mxl[i][n-1-j-mid] >= j-i+1)
				dp[i] = max(dp[i], (short)(dp[j+1]+2) );
		}
	}
	//for(int i = 0; i < mid; i++)
	//	cerr << dp[i] << " ";
	//cerr << endl;
}

inline void solve()
{
	cin >> s;
	n = s.size();
	fill_mxl();
	fill_dp();
	cout << dp[0] << endl;
}

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T; cin >> T;
	while(T--)
	{
		solve();
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 952 KB Output is correct
7 Correct 1 ms 972 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 844 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 952 KB Output is correct
7 Correct 1 ms 972 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 560 ms 49368 KB Output is correct
11 Correct 223 ms 49396 KB Output is correct
12 Correct 373 ms 49384 KB Output is correct
13 Correct 269 ms 40516 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 952 KB Output is correct
7 Correct 1 ms 972 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 560 ms 49368 KB Output is correct
11 Correct 223 ms 49396 KB Output is correct
12 Correct 373 ms 49384 KB Output is correct
13 Correct 269 ms 40516 KB Output is correct
14 Runtime error 5 ms 3740 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -