Go to diff to previous submission
#include <cstdio> #include <cstring> using namespace std; char buffer[1024]; /*int pocet[512][512][512]; int pocet(int i, int v, int p, int d) { if (v < 0) return 0; if (p == 0 || d == 0) return 1; if (mem[v][p][d] > -1){ return mem[v][p][d]; } if (buffer[i] == '(') // mem[v+1][p-1][d] = pocet(i+1, v+1, p-1, d); return pocet(i+1, v+1, p-1, d); else if (buffer[i] == ')') return pocet(i+1, v-1, p, d-1); mem[v][p][d] = pocet(i+1, v+1, p-1, d) + pocet(i+1, v-1, p, d-1); return mem[v][p][d]; } */ #define MOD 1000000 int pocet[1024][1024]; static inline void init(int n){ for (int i = 0; i < n; i++){ memset(pocet[i], 0x0, n*sizeof(int)); } } int main() { int n; while (scanf("%s%n%*c", buffer, &n) != EOF) { if (buffer[0] == ')'){ printf("0\n"); continue; } init(n+1); pocet[1][1] = 1; for (int i = 1; i <= n; i++){ for (int j = 0; j <= i; j++){ if (buffer[i-1] != ')'){ pocet[i][j] += pocet[i-1][j-1] % MOD; } if (buffer[i-1] != '('){ pocet[i][j] += pocet[i-1][j+1] % MOD; } } } printf("%d\n", pocet[n][0] % MOD); } return 0; }
--- c5.s773.cteam024.fq.cpp.0.fq.cpp +++ c5.s909.cteam024.fq.cpp.0.fq.cpp @@ -1,5 +1,4 @@ #include <cstdio> - -#define MOD 1000000 +#include <cstring> using namespace std; @@ -7,15 +6,32 @@ char buffer[1024]; +/*int pocet[512][512][512]; + int pocet(int i, int v, int p, int d) { if (v < 0) return 0; if (p == 0 || d == 0) return 1; - + if (mem[v][p][d] > -1){ + return mem[v][p][d]; + } if (buffer[i] == '(') - return pocet(i+1, v+1, p-1, d) % MOD; +// mem[v+1][p-1][d] = pocet(i+1, v+1, p-1, d); + return pocet(i+1, v+1, p-1, d); else if (buffer[i] == ')') - return pocet(i+1, v-1, p, d-1) % MOD; + return pocet(i+1, v-1, p, d-1); - return (pocet(i+1, v+1, p-1, d) % MOD) + (pocet(i+1, v-1, p, d-1) % MOD); + mem[v][p][d] = pocet(i+1, v+1, p-1, d) + pocet(i+1, v-1, p, d-1); + return mem[v][p][d]; +} +*/ + +#define MOD 1000000 + +int pocet[1024][1024]; + +static inline void init(int n){ + for (int i = 0; i < n; i++){ + memset(pocet[i], 0x0, n*sizeof(int)); + } } @@ -26,5 +42,28 @@ while (scanf("%s%n%*c", buffer, &n) != EOF) { - printf("%d\n", pocet(0, 0, n/2, n/2) % MOD); + + if (buffer[0] == ')'){ + printf("0\n"); + continue; + } + + + init(n+1); + + pocet[1][1] = 1; + + for (int i = 1; i <= n; i++){ + for (int j = 0; j <= i; j++){ + if (buffer[i-1] != ')'){ + pocet[i][j] += pocet[i-1][j-1] % MOD; + } + if (buffer[i-1] != '('){ + pocet[i][j] += pocet[i-1][j+1] % MOD; + } + } + } + + + printf("%d\n", pocet[n][0] % MOD); }