oj.uz

Submission #725469

# Submission time Handle Problem Language Result Execution time Memory
725469 2023-04-17T13:42:01 Z berr Bowling (BOI15_bow) C++17
49 / 100
 465 ms 3884 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 <= 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;
        }

    }



    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(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 ="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 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;


                            for(int k=sum; 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:21: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]
   21 |     for(int i=0; i<s.size(); i++){
      |                  ~^~~~~~~~~
bow.cpp:30:9: warning: unused variable 'k' [-Wunused-variable]
   30 |     int k=0;
      |         ^

Subtask #1
0 / 16.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 140 ms 3668 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 106 ms 3752 KB Output is correct
2 Correct 130 ms 3668 KB Output is correct
3 Correct 121 ms 3752 KB Output is correct
4 Correct 85 ms 3760 KB Output is correct
5 Correct 84 ms 3660 KB Output is correct
6 Correct 162 ms 3752 KB Output is correct
7 Correct 189 ms 3668 KB Output is correct
8 Correct 175 ms 3768 KB Output is correct
9 Correct 211 ms 3756 KB Output is correct
10 Correct 427 ms 3748 KB Output is correct
11 Correct 441 ms 3752 KB Output is correct
12 Correct 416 ms 3752 KB Output is correct
13 Correct 424 ms 3668 KB Output is correct
14 Correct 430 ms 3752 KB Output is correct
15 Correct 427 ms 3744 KB Output is correct
16 Correct 447 ms 3748 KB Output is correct
17 Correct 450 ms 3668 KB Output is correct
18 Correct 97 ms 3788 KB Output is correct
19 Correct 78 ms 3788 KB Output is correct
20 Correct 91 ms 3676 KB Output is correct
21 Correct 74 ms 3668 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 3752 KB Output is correct
2 Correct 202 ms 3756 KB Output is correct
3 Correct 267 ms 3712 KB Output is correct
4 Correct 213 ms 3668 KB Output is correct
5 Correct 211 ms 3416 KB Output is correct
6 Correct 192 ms 3756 KB Output is correct
7 Correct 185 ms 3756 KB Output is correct
8 Correct 201 ms 3748 KB Output is correct
9 Correct 208 ms 3880 KB Output is correct
10 Correct 465 ms 3764 KB Output is correct
11 Correct 420 ms 3668 KB Output is correct
12 Correct 415 ms 3752 KB Output is correct
13 Correct 402 ms 3884 KB Output is correct
14 Correct 231 ms 3756 KB Output is correct
15 Correct 215 ms 3696 KB Output is correct
16 Correct 248 ms 3788 KB Output is correct
17 Correct 267 ms 3668 KB Output is correct
18 Correct 89 ms 3764 KB Output is correct
19 Correct 95 ms 3752 KB Output is correct
20 Correct 81 ms 3668 KB Output is correct
21 Correct 61 ms 3748 KB Output is correct

Subtask #5
0 / 18.0

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