제출 #339698

#제출 시각아이디문제언어결과실행 시간메모리
339698couplefireMatch (CEOI16_match)C++17
100 / 100
18 ms12012 KiB
#include <bits/stdc++.h>
using namespace std;
int n; string s; string ans;
int dp[100005][26];
bool solve(int l, int r){
    if(l == r+1) return 1;
    if(dp[r][s[l]-'a'] < l) return false;
    int a = dp[r][s[l]-'a'];
    ans[l] = '(', ans[a-1] = ')';
    return solve(l+1, a-2) && solve(a, r);
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> s; n = s.length(); ans.resize(n);
    for(int i = 0; i<n; i++){
        for(int j = 0; j<26; j++){
            dp[i][j] = -1;
            if(s[i]-'a' == j) dp[i][j] = i+1;
            if(i >= 1 && dp[i-1][s[i]-'a']-2 >= 0) dp[i][j] = max(dp[i][j], dp[dp[i-1][s[i]-'a']-2][j]);
        }
    }
    if(!solve(0, n-1)) cout << -1 << endl;
    else cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...