Submission #1174107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174107		LucaIlie	Bowling (BOI15_bow)	C++20	100 / 100	745 ms	3600 KiB

bow

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 10;
const int MAX_A = 10;
const int MAX_P = 300;
int points[MAX_N];
long long 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;

            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][p][a][b];
                        }
                    }
                }
            }
        }

        long long ans = 0;
        for ( int a = 0; a <= 10; a++ ) {
            for ( int b = 0; b <= 10; b++ )
                ans += dp[0][0][a][b];
        }

        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;
}

• Subtask 1: 16 / 16
• Subtask 2: 17 / 17
• Subtask 3: 26 / 26
• Subtask 4: 23 / 23
• Subtask 5: 18 / 18