oj.uz

Submission #725463

# Submission time Handle Problem Language Result Execution time Memory
725463 2023-04-17T13:25:58 Z berr Bowling (BOI15_bow) C++17
49 / 100
 679 ms 3880 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
int dp[11][305][12][12];

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 <= n*30; 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;
        }

    }



    vector<string> all, all3;

    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(int 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(int i='0'; i<='9'; i++){
        for(int l='0'; l-'0'+i-'0'<10; l++){
            string f="xAB";  f[1] = i; f[2] = l;
            
            all3.push_back(f);
            
            f ="A/B"; f[0]=i; f[2] = l;

            all3.push_back(f);

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

            all3.push_back(f);
        }
    }

    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 i=sum; i<305; i++){
                    dp[n-1][i-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;


                            for(int k=10+i+j; k<=300; k++){
                                if(p[ind-1]!=-1 && k!=p[ind-1]) continue;
                                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++){

                            
                            for(int k=ssum; k<=300; k++){
                                if(p[ind-1]!=-1&&k!=p[ind-1]) continue;
                                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);
    
    
    int t; cin >> t;
    while(t--){
        solve();
    }
}

Compilation message

bow.cpp: In function 'long long int check(std::string, std::string)':
bow.cpp:9: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]
    9 |     for(int i=0; i<s.size(); i++){
      |                  ~^~~~~~~~~
bow.cpp: In function 'long long int gs(std::string)':
bow.cpp:20: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]
   20 |     for(int i=0; i<s.size(); i++){
      |                  ~^~~~~~~~~
bow.cpp:29:9: warning: unused variable 'k' [-Wunused-variable]
   29 |     int k=0;
      |         ^

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 3660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 159 ms 3768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 3752 KB Output is correct
2 Correct 179 ms 3692 KB Output is correct
3 Correct 166 ms 3756 KB Output is correct
4 Correct 113 ms 3776 KB Output is correct
5 Correct 98 ms 3692 KB Output is correct
6 Correct 215 ms 3768 KB Output is correct
7 Correct 310 ms 3760 KB Output is correct
8 Correct 229 ms 3668 KB Output is correct
9 Correct 302 ms 3764 KB Output is correct
10 Correct 611 ms 3756 KB Output is correct
11 Correct 601 ms 3756 KB Output is correct
12 Correct 603 ms 3760 KB Output is correct
13 Correct 679 ms 3752 KB Output is correct
14 Correct 604 ms 3848 KB Output is correct
15 Correct 632 ms 3760 KB Output is correct
16 Correct 618 ms 3788 KB Output is correct
17 Correct 616 ms 3752 KB Output is correct
18 Correct 109 ms 3668 KB Output is correct
19 Correct 99 ms 3660 KB Output is correct
20 Correct 115 ms 3764 KB Output is correct
21 Correct 94 ms 3668 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 3780 KB Output is correct
2 Correct 261 ms 3788 KB Output is correct
3 Correct 312 ms 3720 KB Output is correct
4 Correct 241 ms 3732 KB Output is correct
5 Correct 274 ms 3404 KB Output is correct
6 Correct 226 ms 3828 KB Output is correct
7 Correct 254 ms 3760 KB Output is correct
8 Correct 229 ms 3760 KB Output is correct
9 Correct 294 ms 3756 KB Output is correct
10 Correct 550 ms 3880 KB Output is correct
11 Correct 494 ms 3780 KB Output is correct
12 Correct 511 ms 3668 KB Output is correct
13 Correct 451 ms 3756 KB Output is correct
14 Correct 276 ms 3668 KB Output is correct
15 Correct 278 ms 3760 KB Output is correct
16 Correct 326 ms 3760 KB Output is correct
17 Correct 333 ms 3752 KB Output is correct
18 Correct 111 ms 3668 KB Output is correct
19 Correct 111 ms 3668 KB Output is correct
20 Correct 100 ms 3764 KB Output is correct
21 Correct 79 ms 3760 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 3660 KB Output isn't correct
2 Halted 0 ms 0 KB -