Go to diff to previous submission
#include <cstdio> #include <cmath> #include <cstdio> #include <cstring> #include <iomanip> #include <iostream> #include <limits.h> #include <map> #include <queue> #include <vector> #include <set> #include <stack> #include <bitset> #include <string> using namespace std; typedef pair<int,int> ii; typedef vector<int> vi; typedef vector<ii> vii; typedef set<int> si; typedef set<ii> sii; #define MP make_pair #define PB push_back #define REP(i,a) for ( int i = 0; i < int(a); i++) #define FOR(i,a,b) for ( int i = int(a); i<=int(b); i++) #define FORD(i,a,b) for(int i= int(a); i>=int(b); i--) const int INF = 1<<29; typedef long long int ll; char line[1024]; int len, half; const int MOD = 1000000; int tab[1002][504]; int rec(int misto, int idx, int five){ int out = 0; //printf("%d %d\n", misto, idx); if ( five >half) return 0; if ( tab[misto][idx] >= 0 ) return tab[misto][idx]; /*if ( idx >= half ) { return 1; }*/ if ( misto >= len -1) { return idx==1 && line[misto] != '(' ; } if (line[misto] == '.' ) { if ( idx == 0 ) out += rec(misto+1, idx+1, five+1); else { out += rec(misto+1, idx+1, five+1); out += rec(misto+1, idx-1, five); } } else if ( line[misto] == '(' ) { out += rec(misto+1, idx+1, five+1); } else { if ( idx == 0 ) return 0; out += rec(misto+1, idx-1, five); } tab[misto][idx] = out%MOD; return out%MOD; } void clear(){ FOR(i,0,len) FOR(j,0,half+1) tab[i][j]=-1; } int main(){ while ( scanf(" %s", line) > 0 ) { len = strlen(line); half = len/2; clear(); printf("%d\n", rec(0,0,0)) ; } return 0; }
--- c5.s743.cteam013.fq.cpp.0.fq.cpp +++ c5.s783.cteam013.fq.cpp.0.fq.cpp @@ -38,10 +38,10 @@ int out = 0; //printf("%d %d\n", misto, idx); - if ( five > half) return 0; + if ( five >half) return 0; if ( tab[misto][idx] >= 0 ) return tab[misto][idx]; - if ( idx >= half ) { + /*if ( idx >= half ) { return 1; - } + }*/ if ( misto >= len -1) { return idx==1 && line[misto] != '(' ;