oj.uz

Submission #67322

# Submission time Handle Problem Language Result Execution time Memory
67322 2018-08-14T02:33:52 Z MatheusLealV Match (CEOI16_match) C++17
10 / 100
 2000 ms 748 KB 
#include <bits/stdc++.h>
#define N 1050
using namespace std;

int n, v[N], dp[N][N], prox[N][N];

string s;

char resp[N];

bool solve(int l, int r)
{
	if(r < l) return true;

	if(r - l == 1) return (v[l] == v[r]);

	if(l == r) return false;

	prox[l][r] = -1;

	for(int j = l + 1; j <= r; j++)
	{
		if(v[l] == v[j])
		{
			if(solve(l + 1, j - 1) and solve(j + 1, r))
			{
				prox[l][r] = j;
			}
		}
	}

	if(prox[l][r] == - 1) return false;

	return true;
}

void getans(int l, int r)
{
	if(r < l) return;

	if(l == r - 1)
	{
		resp[l] = '(', resp[r] = ')';

		return;
	}

	resp[l] = '(';

	resp[prox[l][r]] = ')';

	getans(l + 1, prox[l][r] - 1), getans(prox[l][r] + 1, r);
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>s;

	n = s.size();

	for(int i = 1; i <= n; i++) v[i] = s[i - 1] - 'a';

	if(solve(1, n))
	{
		getans(1, n);

		for(int i = 1; i<= n; i++) cout<<resp[i];

		cout<<"\n";
	}

	else cout<<"-1\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Execution timed out 2069 ms 748 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Execution timed out 2069 ms 748 KB Time limit exceeded
5 Halted 0 ms 0 KB -