oj.uz

Submission #608772

# Submission time Handle Problem Language Result Execution time Memory
608772 2022-07-27T10:00:13 Z Vanilla Match (CEOI16_match) C++17
10 / 100
 246 ms 16028 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 9 ms 15968 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 9 ms 15968 KB Output is correct
4 Incorrect 246 ms 16028 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 9 ms 15968 KB Output is correct
4 Incorrect 246 ms 16028 KB Output isn't correct
5 Halted 0 ms 0 KB -