oj.uz

답안 #134253

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
134253 2019-07-22T09:50:50 Z imyujin 괄호 문자열 (CEOI16_match) C++14
10 / 100
 207 ms 504 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);
		return;
	}
}

int main() {
	int N;

	cin >> s;

	for(N = 0; s[N]; N++);
	for(int i = 0; i < N; i++) dp[i + 1][i] = 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
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 256 KB Output is correct
3 Correct 3 ms 376 KB Output is correct

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 256 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Runtime error 207 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 256 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Runtime error 207 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -