oj.uz

Submission #134176

# Submission time Handle Problem Language Result Execution time Memory
134176 2019-07-22T07:55:32 Z 임유진(#3231) Match (CEOI16_match) C++14
0 / 100
 2 ms 256 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;

char s[MAXN];
bool dp[MAXN][MAXN];
char ans[MAXN];

void solve(int l, int r) {
	if(l > r) return;
	for(int i = r; ; i--) if(s[l] == s[i] && dp[l + 1][i - 1] && dp[i + 1][r]) {
		ans[l] = '(';
		ans[i] = ')';
		solve(l + 1, i - 1);
		solve(i + 1, r);
	}
}

int main() {
	int N;

	cin >> s;

	for(N = 0; s[N]; N++);
	for(int i = 1; i < N; i++) dp[i][i - 1] = true;
	for(int i = 2; i <= N; i++) for(int j = 0; i + j - 1 < N; j++) {
		for(int k = j + 1; k <= i + j - 1; k++) if(s[j] == s[k] && dp[j + 1][k - 1] && dp[k + 1][i +j - 1]) 
			dp[j][i + j - 1] = true;
	}

	if(!dp[0][N - 1]) cout << -1;
	else {
		solve(0, N - 1);
		for(int i = 0; i < N; i++) cout << ans[i];
	}
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -