oj.uz

Submission #609727

# Submission time Handle Problem Language Result Execution time Memory
609727 2022-07-27T19:57:54 Z DanerZein Match (CEOI16_match) C++14
10 / 100
 2000 ms 16204 KB 
#include <bits/stdc++.h>
using namespace std;
int n;
string x;
string ans;
int dp[2010][2010];
bool check(int l,int r){
  if(dp[l][r]!=-1) return dp[l][r];
  if(l>r) return 1;
  bool ok=0;
  for(int i=l+1;i<=r;i++){
    if(x[l]==x[i]){
      ok|=(check(l+1,i-1)&check(i+1,r));
    }
  }
  return dp[l][r]=ok;
}
void match(int l,int r){
  if(l>=r){
    return;
  }
  int id=-1;
  for(int i=r;i>l;i--){
    if(x[i]==x[l] && check(i+1,r)){
      id=i;
      break;
    }
  }
  ans[l]='('; ans[id]=')';
  match(l+1,id-1);
  match(id+1,r);
}
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  memset(dp,-1,sizeof dp);
  cin>>x;
  n=x.size();
  if(check(0,n-1)){
    ans.resize(n);
    match(0,n-1);
    cout<<ans<<endl;
  }
  else cout<<"-1\n";
  
}

Compilation message

match.cpp: In function 'bool check(int, int)':
match.cpp:16:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   16 |   return dp[l][r]=ok;
      |          ~~~~~~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16084 KB Output is correct
2 Correct 8 ms 16136 KB Output is correct
3 Correct 7 ms 16136 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16084 KB Output is correct
2 Correct 8 ms 16136 KB Output is correct
3 Correct 7 ms 16136 KB Output is correct
4 Correct 499 ms 16140 KB Output is correct
5 Correct 183 ms 16204 KB Output is correct
6 Execution timed out 2074 ms 16084 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16084 KB Output is correct
2 Correct 8 ms 16136 KB Output is correct
3 Correct 7 ms 16136 KB Output is correct
4 Correct 499 ms 16140 KB Output is correct
5 Correct 183 ms 16204 KB Output is correct
6 Execution timed out 2074 ms 16084 KB Time limit exceeded
7 Halted 0 ms 0 KB -