Go to diff to previous submission
#include <iostream> #include <set> #include <stdio.h> #include <utility> #include <map> #include <string> #include <sstream> #include <algorithm> #include <vector> using namespace std; const long long m = 1000000; int main(){ string s; while(cin >> s){ long long N = s.size(); vector<vector<long long> > A(N+2, vector<long long>(N+2)); A[N-1][0] = 1; if(s[N-1] == '(' || s[0] == ')'){ cout << 0 << '\n'; continue; } for(int i=N-2; i>=0; --i){ for(int j=0; j<N-i+1; ++j){ if(j == 0){ if(s[i+1] == ')'){ A[i][j] = 0; } else{ A[i][j] = A[i+1][j+1]; } } else{ if(s[i+1] == '('){ A[i][j] = A[i+1][j+1]; } else if(s[i+1] == ')'){ A[i][j] = A[i+1][j-1]; } else{ A[i][j] = (A[i+1][j+1] + A[i+1][j-1]) % m; } } } } cout << A[0][1] % m << '\n'; } return 0; }
--- c5.s680.cteam026.fq.cpp.0.fq.cpp +++ c5.s776.cteam026.fq.cpp.0.fq.cpp @@ -10,5 +10,5 @@ using namespace std; -const long long m = 100000; +const long long m = 1000000; int main(){ @@ -16,5 +16,5 @@ while(cin >> s){ long long N = s.size(); - vector<vector<long long> > A(N+1, vector<long long>(N+1)); + vector<vector<long long> > A(N+2, vector<long long>(N+2)); A[N-1][0] = 1; if(s[N-1] == '(' || s[0] == ')'){