Submission #1174106

#TimeUsernameProblemLanguageResultExecution timeMemory
1174106LucaIlieBowling (BOI15_bow)C++20
33 / 100
281 ms2028 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_N = 10; const int MAX_A = 10; const int MAX_P = 300; const int MOD = 1e9 + 7; int points[MAX_N]; int dp[MAX_N + 1][MAX_P + 1][MAX_A + 1][MAX_A + 1]; vector<pair<string, int>> normalRound, finalRound; bool comp( string a, string b ) { if ( a.size() != b.size() ) return false; bool ok = true; for ( int i = 0; i < a.size(); i++ ) { if ( a[i] == '?' || b[i] == '?' ) continue; ok &= (a[i] == b[i]); } return ok; } void initRounds() { for ( int a = 0; a <= 10; a++ ) { if ( a == 10 ) normalRound.push_back( { "x-", 10 } ); else { string s = ""; s += char( a + '0' ); for ( int b = 0; b <= 10 - a; b++ ) { if ( a + b == 10 ) normalRound.push_back( { s + "/", 10 } ); else { s += char( b + '0' ); normalRound.push_back( { s, a + b } ); s.pop_back(); } } } } for ( int a = 0; a <= 10; a++ ) { string s = ""; int p = a, r = 10; if ( a == 10 ) s += 'x'; else s += char( a + '0' ), r = 10 - a; for ( int b = 0; b <= r; b++ ) { int r2; p += b; if ( a == 10 && b == 10 ) s += 'x', r2 = 10; else if ( b == r ) s += '/', r2 = 10; else if ( a + b >= 10 ) s += char( b + '0' ), r2 = 10 - b; else { s += char( b + '0' ), r2 = -1; s += '-'; finalRound.push_back( { s, p } ); s.pop_back(); } for ( int c = 0; c <= r2; c++ ) { p += c; if ( (b == 10 || (a < 10 && a + b == 10)) && c == 10 ) s += 'x'; else if ( c == r2 ) s += '/'; else s += char( c + '0' ); finalRound.push_back( { s, p } ); p -= c; s.pop_back(); } p -= b; s.pop_back(); } } /* cout << "final\n"; for ( auto x: finalRound ) cout << x.first << " " << x.second << "\n"; cout << "normal\n"; for ( auto x: normalRound ) cout << x.first << " " << x.second << "\n"; */ } int main() { cin.tie( nullptr ); ios_base::sync_with_stdio( false ); int t; initRounds(); cin >> t; while ( t-- ) { int n; string s; cin >> n >> s; for ( int i = 0; i < n; i++ ) cin >> points[i]; for ( auto x: finalRound ) { string ss = ""; for ( int i = s.size() - 3; i < s.size(); i++ ) ss += s[i]; if ( !comp( ss, x.first ) ) continue; //cout << "comp " << x.first << " " << x.second << "\n"; int a = (x.first[0] == 'x' ? 10 : x.first[0] - '0'); int b = (x.first[1] == 'x' ? 10 : (x.first[1] == '/' ? 10 - a : x.first[1] - '0')); for ( int p = x.second; p <= MAX_P; p++ ) dp[n - 1][p - x.second][a][b] += (points[n - 1] == -1 ? 1 : (p == points[n - 1])); } for ( int a = 0; a <= 10; a++ ) { for ( int b = 0; b <= 10; b++ ) { for ( int p = 0; p <= MAX_P; p++ ) { if ( dp[n - 1][p][a][b] == 0 ) continue; } } } for ( int i = n - 1; i >= 1; i-- ) { //tranzitionez de la i la i + 1; if ( points[i - 1] != -1 ) { for ( int a = 0; a <= 10; a++ ) { for ( int b = 0; b <= 10; b++ ) { for ( int p = 0; p <= MAX_P; p++ ) { if ( p != points[i - 1] ) dp[i][p][a][b] = 0; //printf( "%d %d %d %d: %d\n", i, p, a, b, dp[i][p][a][b] ); } } } } vector<pair<string, int>> okStates; for ( auto x: normalRound ) { string ss = ""; for ( int j = i * 2 - 2; j < i * 2; j++ ) ss += s[j]; if ( comp( ss, x.first ) ) okStates.push_back( x ); } for ( int p = 0; p <= MAX_P; p++ ) { for ( int a = 0; a <= 10; a++ ) { for ( int b = 0; b <= 10; b++ ) { if ( dp[i][p][a][b] == 0 ) continue; //printf( "dp %d %d %d %d: %d\n", i, p, a, b, dp[i][p][a][b] ); for ( auto x: okStates ) { int crtP = x.second; if ( x.first[0] == 'x' ) crtP += a + b; else if ( x.first[1] == '/' ) crtP += a; if ( p < crtP ) continue; int newA = a, newB = b; if ( x.first[0] == 'x' ) { newA = 10; newB = a; } else { newA = x.first[0] - '0'; newB = x.second - newA; } //printf( "ceba %c %d %d %d\n", x.first[0], x.second, newA, newB ); dp[i - 1][p - crtP][newA][newB] = (dp[i - 1][p - crtP][newA][newB] + dp[i][p][a][b]) % MOD; } } } } } int ans = 0; for ( int a = 0; a <= 10; a++ ) { for ( int b = 0; b <= 10; b++ ) ans = (ans + dp[0][0][a][b]) % MOD; } cout << ans << "\n"; for ( int i = 0; i <= n; i++ ) { for ( int p = 0; p <= MAX_P; p++ ) { for ( int a = 0; a <= 10; a++ ) { for ( int b = 0; b <= 10; b++ ) dp[i][p][a][b] = 0; } } } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...