Submission #2457249

---

Source Code Expand

#include <iostream>
#include <string>
#include <cstring>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)

using ll = long long;

std::string S;
ll ans = 1<<30;
bool dp[110][110][110];

void dfs( int i, ll last, ll cnt, ll diff )
{
  if( diff < 0 )
    return;

  if( dp[last][cnt][diff] )
    return;

  if( i == S.size() )
  {
    if( !diff )
      ans = std::min( ans, cnt+last );

    return;
  }

  dfs( i+1, last, cnt, diff+(S[i]=='('?1:-1) );

  dfs( i+1, i, cnt+1, diff+(S[i]=='('?-1:1) );

  dp[last][cnt][diff] = true;

  return;
}

int main()
{
  std::cin >> S;

  dfs( 0, 0, 0, 0 );

  std::cout << ans << std::endl;

  return 0;
}

Submission Info

Judge Result