oj.uz

답안 #77752

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
77752 2018-09-30T08:11:49 Z triplem5ds 괄호 문자열 (CEOI16_match) C++14
10 / 100
 23 ms 2548 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int,int>;
using ll = long long;

const int N = 1e5+5;
const int mod = 1e9 + 7;

int dp[505][505], n;
string str;
int solve(int l, int r){
    if( l > r )
        return 1;
    int &ret = dp[l][r];

    if(~ret)
        return ret;
    ret = 0;
    for(int i = r; i > l; --i)
        if(str[i] == str[l] && solve(l+1,i-1) && solve(i+1,r)){
            return ret = 1;
        }
    return ret;
}
void trace(int l, int r){
    if(l > r)return;
    for(int i = r; i > l; --i){
        if(str[i] == str[l] && solve(l+1,i-1) && solve(i+1,r)){
            cout << "(";
            trace(l+1,i-1);
            cout << ")";
            trace(i+1,r);
            return;
        }
    }
    assert(false);
}
int main(){
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif // ONLINE_JUDGE

    cin >> str; n = str.size();

    if(n & 1)return puts("-1");
    memset(dp,-1,sizeof dp);
    if(!solve(0,n-1)){
        cout << -1 << '\n';
    }   else {
        trace(0,n-1);
    }

    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1272 KB Output is correct
2 Correct 3 ms 1536 KB Output is correct
3 Correct 3 ms 1536 KB Output is correct
4 Runtime error 23 ms 2548 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 3 ms 1272 KB Output is correct
2 Correct 3 ms 1536 KB Output is correct
3 Correct 3 ms 1536 KB Output is correct
4 Runtime error 23 ms 2548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -