oj.uz

Submission #77753

# Submission time Handle Problem Language Result Execution time Memory
77753 2018-09-30T08:26:43 Z triplem5ds Match (CEOI16_match) C++14
37 / 100
 12 ms 1748 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 532 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 532 KB Output is correct
4 Correct 3 ms 748 KB Output is correct
5 Correct 3 ms 748 KB Output is correct
6 Correct 8 ms 920 KB Output is correct
7 Correct 12 ms 1052 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 532 KB Output is correct
4 Correct 3 ms 748 KB Output is correct
5 Correct 3 ms 748 KB Output is correct
6 Correct 8 ms 920 KB Output is correct
7 Correct 12 ms 1052 KB Output is correct
8 Runtime error 5 ms 1748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -