fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MOD = 1e9+7;
  4. const int MAXN = 1010;
  5.  
  6. int N;
  7. int DP[MAXN][MAXN];
  8. char S[MAXN];
  9.  
  10. int solve(const int idx, const int opened1, const int opened2) {
  11.    if (idx == N)
  12.       return opened1 == 0 && opened2 == 0;
  13.    if (opened1 < 0 || opened2 < 0)
  14.       return 0;
  15.    if (DP[idx][opened1] != -1)
  16.       return DP[idx][opened1];
  17.    DP[idx][opened1] = (solve(idx + 1, opened1 + (S[idx] == '[' ? 1 : -1), opened2) +
  18.                        solve(idx + 1, opened1, opened2 + (S[idx] == '[' ? 1 : -1))) % MOD;
  19.    return DP[idx][opened1];
  20. }
  21.  
  22. int main() {
  23.    while (scanf(" %s", S) == 1) {
  24.       N = strlen(S);
  25.       memset(DP, -1, sizeof(DP));
  26.       printf("%d\n", solve(0, 0, 0));
  27.    }
  28.    return 0;
  29. }
  30.  
Success #stdin #stdout 0s 19216KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tPc11o
language:
C++14 (clang 8.0)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!