Submission #609727

#	Time	Username	Problem	Language	Result	Execution time	Memory
609727		DanerZein	Match (CEOI16_match)	C++14	10 / 100	2074 ms	16204 KiB

match

#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 (stderr)

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 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 63