Submission #608772

#	Time	Username	Problem	Language	Result	Execution time	Memory
608772		Vanilla	Match (CEOI16_match)	C++17	10 / 100	246 ms	16028 KiB

match

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long int64;
const int maxn = 2e3 + 2;
int dp[maxn][maxn];
string rs;
string s;
int n;

bool solve (int l, int r) {
    if (l > r) return 1;
    if ((r - l + 1) % 2 == 1) return 0;
    if (dp[l][r] != -1) return dp[l][r];
    dp[l][r] = 0;
    if (s[l] == s[r]) {
        rs[l] = '(', rs[r] = ')';
        return dp[l][r] = solve(l + 1, r - 1);
    }
    for (int i = l + 1; i < r; i++){
        dp[l][r] |= (solve(l, i) & solve(i + 1, r));
    }
    return dp[l][r];
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> s;
    n = s.size();
    rs = string(n, '0');
    memset(dp, -1, sizeof(dp));
    solve(0, n - 1);
    for (char c: rs) {
        if (c == '0') {
            cout << "-1";
            return 0;
        }
    }
    stack <char> st;
    for (char c: rs) {
        if (c == ')' && !st.empty() && st.top() == '(') {
            st.pop();
        }
        else st.push(c);
    }
    cout << (st.empty() ? rs: "-1");
    return 0;
}

Compilation message (stderr)

match.cpp: In function 'bool solve(int, int)':
match.cpp:19:25: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   19 |         return dp[l][r] = solve(l + 1, r - 1);
      |                ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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