Submission #77753

#	Time	Username	Problem	Language	Result	Execution time	Memory
77753		triplem5ds	Match (CEOI16_match)	C++14	37 / 100	12 ms	1748 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;

bitset<2005> dp[2005];
int n;
string str;
int solve(int l, int r){
    if( l > r )
        return 1;
   return dp[l][r];
}
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");

    for(int i = 0; i < n; i++)
        dp[i+1][i] = 1;

    for(int l = n-1; l >= 0; --l){

        vector<int>toOr;

        for(int r = l + 1; r < n; ++r)
            if(str[l] == str[r] && solve(l+1,r-1)){
                toOr.push_back(r+1);
            }
        ///dp[l][i] = orIng of dp[v1][i]
        ///where v1 and v2 and v3 are in the toOr
        for(auto x : toOr)
            dp[l] |= dp[x];

    }
    if(!solve(0,n-1)){
        cout << -1 << '\n';
    }   else {
        trace(0,n-1);
    }

    return 0;
}

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