Submission #2457280

---

Source Code Expand

#include <algorithm>
#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)
#define clr(a,v) memset((a),(v),sizeof(a))

using ll = long long;

std::string S;
ll dp[110][110][110];
constexpr ll INF = 1<<30;

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

  ll &ret = dp[i][last][diff];

  if( ret != -1 )
    return ret;

  ret = INF;

  if( i == S.size() )
  {
    if( !diff )
      return ret = last-i;
    else
      return INF;
  }

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

  ret = std::min( ret, dfs( i+1, i, diff+(S[i]=='('?-1:1) )+2 );

  return ret;
}

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

  clr( dp, -1 );
  std::cout << dfs( 0, 0, 0 ) << std::endl;

  return 0;
}

Submission Info

Judge Result