Go to diff to previous submission
#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <algorithm> #include <utility> #include <string> #include <deque> #include <list> #include <map> #include <queue> #include <set> #include <stack> #include <vector> using namespace std; //#define debug printf #define debug blackhole void blackhole(...) {} #define MOD 1000000 char line[2000]; int table[2000][2000]; void solve() { if (strlen(line)%2 == 1) { printf("0\n"); return; } for (int i = 0; line[i]; i++) { for (int j = 0; line[j]; j++) { table[i][j] = 0; } } table[0][0] = 1; int len = strlen(line); for (int j = 1; j <= len/2; j++) { if (line[j - 1] == ')') { table[0][j] = 0; } else { table[0][j] = table[0][j - 1]; } } for (int i = 1; i <= len/2; i++) { if (line[i * 2 - 1] == ')' || line[i * 2 - 1] == '.') { table[i][i] = table[i-1][i]; } else { table[i][i] = 0; } for (int j = i + 1; j <= len/2; j++) { table[i][j] = 0; int index = i + j - 1; char c = line[index]; if (c == ')' || c == '.') { table[i][j] = (table[i][j] + table[i-1][j]) % MOD; } if (c == '(' || c == '.') { table[i][j] = (table[i][j] + table[i][j-1]) % MOD; } } } for (int i=0;i<=len/2;i++) { for (int j=0;j<=len/2;j++) { debug("%d\t", table[i][j]); } debug("\n"); } debug("\n"); printf("%d\n", table[len/2][len/2]); } int main() { while (true) { if (scanf("%s", line) != 1) break; debug("line: %s\n", line); solve(); } return 0; }
--- c5.s958.cteam032.fq.cpp.0.fq.cpp +++ c5.s961.cteam032.fq.cpp.0.fq.cpp @@ -21,6 +21,6 @@ #define MOD 1000000 -char line[10000]; -int table[10000][10000]; +char line[2000]; +int table[2000][2000]; void solve() { @@ -30,6 +30,6 @@ } - for (int i = 0; i < 10000; i++) { - for (int j = 0; j < 10000; j++) { + for (int i = 0; line[i]; i++) { + for (int j = 0; line[j]; j++) { table[i][j] = 0; }