Submission #205661

#	Time	Username	Problem	Language	Result	Execution time	Memory
205661		Atill83	Bowling (BOI15_bow)	C++14	100 / 100	739 ms	7164 KiB

bow

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n;
ll ali[MAXN];

struct turn{
    char a, b, c;
} t[15];

ll dp[15][15][15][305];
bool did[15][15][15][305];

bool isa(char a){
    return (a >= '0' && a <= '9');
}

char table[15] = "0123456789x/-";
ll do_it(int trn, ll needed, ll atis1, ll atis2){        
    if(needed < 0) return 0;
    if(trn == 0 && (needed == 0 || needed == 301)){return 1;}
    if(did[trn][atis1][atis2][needed]){ return dp[trn][atis1][atis2][needed];}
    did[trn][atis1][atis2][needed] = 1;
    int fr = needed;
    if(ali[trn] != -1){
        if(needed == 301){
            needed = ali[trn];
        }else if(needed != ali[trn]){
            return dp[trn][atis1][atis2][fr] = dp[trn][atis1][atis2][needed]  = 0;
        }
    }
    if(fr != needed){
        if(did[trn][atis1][atis2][needed]){return dp[trn][atis1][atis2][fr] = dp[trn][atis1][atis2][needed];}
        did[trn][atis1][atis2][needed] = 1;
    }
    turn dis = t[trn];
    if(dis.c == 'h'){
        if(dis.a == '?' && dis.b == '?'){
            ll ans = 0;
            for(int i = 0; i < 10; i++){
                ans += do_it(trn - 1, (needed == 301 ? 301 : needed - 10 - atis1), i, 10 - i);
                for(int j = 0; i + j < 10; j++){
                    ans += do_it(trn - 1, (needed == 301 ? 301 : needed - i - j), i, j);
                }
            }
            ans += do_it(trn - 1, (needed == 301 ? 301 : needed - 10 - atis1 - atis2),10, atis1);
            return dp[trn][atis1][atis2][fr] = dp[trn][atis1][atis2][needed]  = ans;
        }else if(dis.a == '?'){
            if(dis.b == '/'){
                ll ans = 0;
                for(int i = 0; i < 10; i++){
                    ans += do_it(trn - 1, (needed == 301 ? 301: needed - 10 - atis1), i, 10 - i);
                }
                return dp[trn][atis1][atis2][fr] = dp[trn][atis1][atis2][needed]  = ans;
            }else if(dis.b == '-'){
                return dp[trn][atis1][atis2][fr] = dp[trn][atis1][atis2][needed]  = do_it(trn - 1, (needed == 301 ? 301: needed - 10 - atis1 - atis2), 10, atis1);
            }else if(isa(dis.b)){
                ll sec = dis.b - '0';
                ll ans = 0;
                for(int i = 0; i + sec < 10; i++){
                    ans += do_it(trn - 1, (needed == 301 ? 301: needed - sec - i), i, sec);
                }
                return dp[trn][atis1][atis2][fr] = dp[trn][atis1][atis2][needed]  = ans;
            }else{
                return 0;
            }
        }else if(dis.b == '?'){
            if(dis.a == 'x'){
                return dp[trn][atis1][atis2][fr] = dp[trn][atis1][atis2][needed]  = do_it(trn - 1, (needed == 301 ? 301: needed - 10 - atis1 - atis2), 10, atis1);
            }else if(isa(dis.a)){
                ll ans = 0;
                ll ilk = dis.a - '0';
                for(int i = 0; i + ilk < 10; i++){
                    ans += do_it(trn - 1,(needed == 301 ? 301: needed - ilk - i), ilk, i);
                }
                ans += do_it(trn - 1, (needed == 301 ? 301: needed - 10 - atis1), ilk, 10 - ilk);
                
                return dp[trn][atis1][atis2][fr] = dp[trn][atis1][atis2][needed] = ans;
            }else{
                return 0;
            }
        }else{
            if(dis.a == 'x' && dis.b == '-'){
                return dp[trn][atis1][atis2][fr] = dp[trn][atis1][atis2][needed]  = do_it(trn - 1, (needed == 301 ? 301: needed - 10 - atis1 - atis2), 10, atis1);
            }else if(isa(dis.a) && dis.b == '/'){
                ll ilk = dis.a - '0';
                //cout<<atis1<<" "<<needed<<endl;
                ll ans = do_it(trn - 1, (needed == 301 ? 301: needed - 10 - atis1), ilk, 10 - ilk);
                //cout<<ans<<endl;
                return dp[trn][atis1][atis2][fr] = dp[trn][atis1][atis2][needed]  =ans;
            }else if(isa(dis.a) && isa(dis.b)){
                ll ilk = dis.a - '0';
                ll iki = dis.b - '0';
                ll ans = do_it(trn - 1, (needed == 301 ? 301: needed -ilk - iki), ilk, iki);
                return dp[trn][atis1][atis2][fr] = dp[trn][atis1][atis2][needed] = ans;
            }else{
                return 0;
            }
        }
    }else{
        char a, b ,c;
        for(int i = 0; i < (dis.a == '?' ? 11 : 1); i++){
            for(int j = 0; j < (dis.b == '?' ? 12 : 1); j++){
                for(int k = 0; k < (dis.c == '?' ? 13 : 1); k++){
                    if(dis.a == '?'){
                        a = table[i];
                    }else{
                        a = dis.a;
                    }
                    if(dis.b == '?'){
                        b = table[j];
                    }else{
                        b = dis.b;
                    }
                    if(dis.c == '?'){
                        c = table[k];
                    }else{
                        c = dis.c;
                    }
                    if(a == 'x'){
                        if(b == 'x'){
                            if(c == 'x'){
                                ll ans = do_it(trn - 1, (needed == 301 ? 301: needed - 30), 10, 10);
                                //cout<<trn - 1<<" "<<(needed == 301 ? 301: needed - 30)<<endl;
                                //cout<<ans<<endl;
                                dp[trn][atis1][atis2][needed]  += ans;
                                dp[trn][atis1][atis2][fr] = dp[trn][atis1][atis2][needed];
                            }
                            else if(isa(c)){
                                ll deg = (int) (c - '0');
                                ll ans = do_it(trn - 1, (needed == 301 ? 301:needed - 20 - deg), 10, 10);
                                
                                dp[trn][atis1][atis2][needed]  += ans;
                                dp[trn][atis1][atis2][fr] = dp[trn][atis1][atis2][needed];
                            }
                        }else if(isa(b)){
                            if(c == '/'){
                                ll cur = (int)(b - '0');//xA/
                                ll ans = do_it(trn - 1,(needed == 301 ? 301:needed - 20), 10, cur);
                                //if(ans) cout<<ans<<endl;
                                dp[trn][atis1][atis2][needed]  += ans;
                                dp[trn][atis1][atis2][fr] = dp[trn][atis1][atis2][needed];
                            }else if(c >= '0' && c <= '9'){
                                ll ilk = (int)(b - '0');
                                ll iki = (int)(c - '0');
                                ll ans = 0;
                                if(ilk + iki < 10)
                                    ans = do_it(trn - 1, (needed == 301 ? 301: needed - 10 - ilk - iki), 10, ilk);
                                
                                dp[trn][atis1][atis2][needed]  += ans;
                                dp[trn][atis1][atis2][fr] = dp[trn][atis1][atis2][needed];
                            }
                        }
                    }else if(isa(a)){
                        if(b == '/'){
                            if(c == 'x'){
                                ll ilk = (int) (a -'0');
                                ll ans = do_it(trn - 1, (needed == 301 ? 301: needed - 20), ilk, 10 - ilk);
                                //cout<<trn<<" "<<a<<" "<<b<<" "<<c<<" "<<ans<<endl;
                                dp[trn][atis1][atis2][needed]  += ans;
                                dp[trn][atis1][atis2][fr] = dp[trn][atis1][atis2][needed];
                            }else if(isa(c)){
                                ll ilk = (int) (a - '0');
                                ll iki = (int) (c - '0');
                                ll ans = do_it(trn - 1, (needed == 301 ? 301: needed - 10 - iki), ilk, 10 - ilk);
                                //  cout<<a<<b<<c<<" "<<ans<<endl;
                                dp[trn][atis1][atis2][needed]  += ans;
                                dp[trn][atis1][atis2][fr] = dp[trn][atis1][atis2][needed];
                            }
                        }else if(isa(b) && c == '-'){
                            ll ilk = (int) (a - '0');
                            ll iki = (int) (b - '0');
                            ll ans = 0;
                            if(ilk + iki < 10){
                                ans = do_it(trn - 1, (needed == 301 ? 301:needed - ilk - iki), ilk, iki);
                            }
                            dp[trn][atis1][atis2][needed]  += ans;
                            dp[trn][atis1][atis2][fr] = dp[trn][atis1][atis2][needed];
                        }
                    }
                }
            }
        }
        return dp[trn][atis1][atis2][fr] = dp[trn][atis1][atis2][needed] ;
    }
}




void solve(){
    ll n;
    cin>>n;
    string s;
    cin>>s;
    for(int i = 1; i <= n; i++){
        cin>>ali[i];
    }
    for(int i = 0; i <= 10; i++){
        for(int j = 0; j <= 14; j++){
            for(int k = 0; k <= 14; k++){
                for(int l = 0; l <= 302; l++){
                    dp[i][j][k][l] = 0;
                    did[i][j][k][l] = 0;
                }
            }
        }
    }
    for(int i = 0; i < 2*n - 2; i += 2){
        t[i/2 + 1] = {s[i], s[i + 1], 'h'}; 
    }
    t[n] = {s[2*n - 2],s[2*n - 1], s[2*n]};
    cout<<do_it(n, 301, 0, 0)<<endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("../IO/int.txt","r",stdin);
        freopen("../IO/out.txt","w",stdout);
    #endif
    int q;
    cin>>q;
    while(q--){
        solve();
    }
    

    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}   

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