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 = 100000; int main(){ string s; while(cin >> s){ long long N = s.size(); vector<vector<long long> > A(N+1, vector<long long>(N+1)); 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.s663.cteam026.fq.cpp.0.fq.cpp +++ c5.s680.cteam026.fq.cpp.0.fq.cpp @@ -10,12 +10,11 @@ using namespace std; -const long m = 100000; +const long long m = 100000; int main(){ string s; while(cin >> s){ - int res = 0; - int N = s.size(); - vector<vector<long> > A(N+1, vector<long>(N+1)); + long long N = s.size(); + vector<vector<long long> > A(N+1, vector<long long>(N+1)); A[N-1][0] = 1; if(s[N-1] == '(' || s[0] == ')'){ @@ -41,5 +40,5 @@ } else{ - A[i][j] = A[i+1][j+1] + A[i+1][j-1] % m; + A[i][j] = (A[i+1][j+1] + A[i+1][j-1]) % m; } }