Go to diff to previous submission
#include <cstdlib> #include <cstdio> #include <cstring> #include <cmath> using namespace std; char input[1024]; int tlen; int **reslt; int f(const char *str, int extra, int rem) { if (!rem) return !extra; if (reslt[extra][rem] >= 0) return reslt[extra][rem]; int total = 0; if (str[0] != ')' && str[1] != '(') // ab total += f(str+2, extra, rem-2); if (str[0] != '(' && str[1] != '(' && extra >= 2) // bb total += f(str+2, extra-2, rem-2); if (str[0] != ')' && str[1] != ')') // aa total += f(str+2, extra+2, rem-2); if (str[0] != '(' && str[1] != ')' && extra >= 1) // ba total += f(str+2, extra, rem-2); total %= 1000000; reslt[extra][rem] = total; return total; } int main() { int *inner = new int[1024*1024]; reslt = new int *[1024]; for (int i = 0; i < 1024; i++) reslt[i] = inner+1024*i; do { char cur = getchar(); if (cur != '.' && cur != '(' && cur != ')') break; tlen = 0; while (cur != '\n') { input[tlen++] = cur; cur = getchar(); } if (!tlen) break; input[tlen] = 0; // vstup nacten for (int i = 0; i <= tlen; i++) for (int j = 0; j <= tlen; j++) reslt[i][j] = -1; int result = f(input, 0, tlen); printf("%d\n", result); } while (true); delete [] inner; delete [] reslt; return 0; }
--- c5.s1108.cteam033.fq.cpp.0.fq.cpp +++ c5.s1111.cteam033.fq.cpp.0.fq.cpp @@ -25,5 +25,5 @@ if (str[0] != '(' && str[1] != ')' && extra >= 1) // ba total += f(str+2, extra, rem-2); - total %= 100000; + total %= 1000000; reslt[extra][rem] = total; return total;