Submission #725486

#	Time	Username	Problem	Language	Result	Execution time	Memory
725486		berr	Bowling (BOI15_bow)	C++17	100 / 100	757 ms	3840 KiB

bow

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")

long long 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;
 
    for(int i = 0; i < n; i++){
        for(int l = 0; l <= 300; l++){
            for(int j = 0; j<=10; j++){
                for(int k = 0; k<=10; k++){
                    dp[i][l][j][k]=0;
                }
            }
        }
    }
 
    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]]++;
                }
            }
        }
    }
 
    long long 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 'int check(std::string, std::string)':
bow.cpp:10:19: warning: comparison of integer expressions of different signedness: '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 'int gs(std::string)':
bow.cpp:22:19: warning: comparison of integer expressions of different signedness: '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