oj.uz

답안 #67323

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
67323 2018-08-14T02:34:49 Z MatheusLealV 괄호 문자열 (CEOI16_match) C++17
10 / 100
 2000 ms 25948 KB 
#include <bits/stdc++.h>
#define N 2050
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;

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

	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 dp[l][r] = false;

	return dp[l][r] = 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';

	memset(dp, -1, sizeof dp);

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

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

		cout<<"\n";
	}

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

Compilation message

match.cpp: In function 'bool solve(int, int)':
match.cpp:34:40: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  if(prox[l][r] == - 1) return dp[l][r] = false;
                               ~~~~~~~~~^~~~~~~
match.cpp:36:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  return dp[l][r] = true;
         ~~~~~~~~~^~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 16800 KB Output is correct
2 Correct 17 ms 17016 KB Output is correct
3 Correct 16 ms 17016 KB Output is correct

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 16800 KB Output is correct
2 Correct 17 ms 17016 KB Output is correct
3 Correct 16 ms 17016 KB Output is correct
4 Correct 154 ms 21492 KB Output is correct
5 Correct 26 ms 21492 KB Output is correct
6 Execution timed out 2070 ms 25948 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 16800 KB Output is correct
2 Correct 17 ms 17016 KB Output is correct
3 Correct 16 ms 17016 KB Output is correct
4 Correct 154 ms 21492 KB Output is correct
5 Correct 26 ms 21492 KB Output is correct
6 Execution timed out 2070 ms 25948 KB Time limit exceeded
7 Halted 0 ms 0 KB -