Submission #77752

#	Time	Username	Problem	Language	Result	Execution time	Memory
77752		triplem5ds	Match (CEOI16_match)	C++14	10 / 100	23 ms	2548 KiB

match

#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 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 63