Submission #725479

#	Time	Username	Problem	Language	Result	Execution time	Memory
725479		berr	Bowling (BOI15_bow)	C++17	100 / 100	770 ms	4172 KiB

bow

#include <bits/stdc++.h>
using namespace std;

#define int long long
int dp[11][305][12][12];
vector<string> all, all3;

int check(string t, string s){
    
    for(int i=0; i<s.size(); i++){
        if(s[i]!=t[i]&&s[i]!='?') return 0;

    }
    return 1;

}


int gs(string s){
    if(s.size()==3){
    int k=0;
    for(int i=0; i<s.size(); i++){
        if(s[i]=='x') k+=10;
        else if(s[i]=='/') k+=10-(s[i-1]-'0');
        else if(s[i]!='-') k+=(s[i]-'0');
    }

    return k;
    }

    int k=0;

    if(s[0]=='x') return 10;
    if(s[1]=='/') return 10;
    return (s[0]+s[1]-'0'*2);
}


array<int, 2> ab(string s){
    array<int, 2> q;

    if(s.size()==3){
        if(s[0]=='x') q[0] = 10;
        else q[0]=(s[0]-'0');
        if(s[1]=='x') q[1] = 10;
        else if(s[1]=='/') q[1] = 10-(s[0]-'0');
        else q[1]=(s[1]-'0');

        return q;
    }
    else{
        if(s[1]=='/'){
            return {s[0]-'0', 10-(s[0]-'0')};
        }
        else{
            return {s[0]-'0', s[1]-'0'};
        }
    }
}



void solve(){
    int n; cin >> n;
    string s; cin >> s;
    vector<string> b;

    b.push_back("zort");
    vector<int> p(n);

    for(auto &i: p) cin >> i;

    memset(dp, 0, sizeof(dp));

    string last="00"; 

    for(int i=0; i<2*(n); i+=2){
        string t;

        t+=s[i]; t+=s[i+1];

        if(i/2<n-1) {
            b.push_back(t);
        }

        else{
            t+=s[i+2];
            b.push_back(t);
            last=t;
        }

    }



    for(auto i: all3){
        if(check(i, last)){
            int sum=gs(i);
            auto x=ab(i);
            if(p[n-1] != -1){

                dp[n-1][p[n-1]-sum][x[0]][x[1]]++;
            }
            else{
                for(int l=sum; l<305; l++){
                    dp[n-1][l-sum][x[0]][x[1]]++;
                }
            }
        }
    }

    int ans = 0;


    for(int ind=n-1; ind>0; ind--){
        for(auto l: all){
            if(check(l, b[ind])){

                if(l=="x-"){

    
                    for(int i=0; i<=10; i++){
                        for(int j=0; j<=10; j++){
                            int sum=10+i+j;

                            if(p[ind-1]!=-1){
                                int k=p[ind-1];
                                 int f=k-sum;

                                 if(f>=0){
                                dp[ind-1][f][10][i] += dp[ind][k][i][j]; 
                                if(ind==1&&f==0) ans +=dp[ind][k][i][j];
                                }
                            }
                            else{
                                for(int k=sum; k<=300; k++){
                                    int f=k-sum;
                                    dp[ind-1][f][10][i] += dp[ind][k][i][j]; 
                                    if(ind==1&&f==0) ans +=dp[ind][k][i][j];
                                }   
                            }
                        }
                    }

                }

                else{
                    int sum=gs(l);
                    auto x=ab(l);

                    for(int i=0; i<=10; i++){
                        int ssum=sum;
                        if(l[1]=='/') ssum+=i;
                        for(int j=0; j<=10; j++){

                            
                            if(p[ind-1]!=-1){
                                int k=p[ind-1];
                                int f=k-ssum;

                                if(f>=0){
                                dp[ind-1][f][x[0]][x[1]] +=  dp[ind][k][i][j];

                                if(f==0&&ind==1){
                                    ans+=dp[ind][k][i][j];
                                } 
                                }
                            }
                            else{
                                for(int k=ssum; k<=300; k++){
                                    int f=k-ssum;


                                    dp[ind-1][f][x[0]][x[1]] +=  dp[ind][k][i][j];

                                    if(f==0&&ind==1){
                                        ans+=dp[ind][k][i][j];
                                    } 
                                }
                            }
                        }
                    }

                }

            }
        }
    }


    cout<<ans<<"\n";

}


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    

    all.push_back("x-");
    all3.push_back("xxx");

    for(char i='0'; i<='9'; i++){
        string f="x/";

        f[0]=i;

        all.push_back(f);

        for(char l='0'; l-'0'+i-'0'<10; l++){
            string ff=f;

            ff[1]=l;
            all.push_back(ff);
        }
    }

    for(char i='0'; i<='9'; i++){
        string f="xxA"; f[2] = i;
        
        all3.push_back(f);

        f="A/x"; f[0]=i;
        all3.push_back(f);
    
        f="xA/"; f[1] = i;
        
        all3.push_back(f);
        
    }

    for(char i='0'; i<='9'; i++){
        for(char l='0'; l-'0'+i-'0'<10; l++){
            string f="xAB";  f[1] = i; f[2] = l;
            
            all3.push_back(f);
            
        

            f="AB-"; f[0] = i; f[1]=l;

            all3.push_back(f);
        }
    }


    for(char i='0'; i<='9'; i++){
        for(int l='0'; l<='9'; l++){
            string f ="A/B"; f[0]=i; f[2] = l;

            all3.push_back(f);
        }
    }

    
    int t; cin >> t;
    while(t--){
        solve();
    }
}

Compilation message (stderr)

bow.cpp: In function 'long long int check(std::string, std::string)':
bow.cpp:10:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(int i=0; i<s.size(); i++){
      |                  ~^~~~~~~~~
bow.cpp: In function 'long long int gs(std::string)':
bow.cpp:22:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0; i<s.size(); i++){
      |                  ~^~~~~~~~~
bow.cpp:31:9: warning: unused variable 'k' [-Wunused-variable]
   31 |     int k=0;
      |         ^

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