제출 #67325

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67325		MatheusLealV	괄호 문자열 (CEOI16_match)	C++17	10 / 100	19 ms	17452 KiB

match

#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 = r; j > l; j--)
	{
		if(v[l] == v[j])
		{
			if(solve(l + 1, j - 1) and solve(j + 1, r))
			{
				prox[l][r] = j;


			}

			break;
		}
	}

	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";
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 10 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 63