Submission #339697

#	Time	Username	Problem	Language	Result	Execution time	Memory
339697		couplefire	Match (CEOI16_match)	C++17	100 / 100	20 ms	12160 KiB

match

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005

int n; string s;
string ans;
int dp[MAXN][26];

bool solve(int l, int r){
    if(l == r+1) return 1;
    if(dp[r][s[l]-'a'] < l) return false;
    ans[l] = '(', ans[dp[r][s[l]-'a']-1] = ')';
    return solve(l+1, dp[r][s[l]-'a']-2) && solve(dp[r][s[l]-'a'], r);
}

int main(){
    // freopen("match.in", "r", stdin);
    // freopen("match.out", "w", stdout);
    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;
}

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