oj.uz

Submission #725470

# Submission time Handle Problem Language Result Execution time Memory
725470 2023-04-17T13:43:10 Z berr Bowling (BOI15_bow) C++17
49 / 100
 443 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 <= 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(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 ="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 3756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 133 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 87 ms 3748 KB Output is correct
2 Correct 136 ms 3796 KB Output is correct
3 Correct 117 ms 3748 KB Output is correct
4 Correct 89 ms 3752 KB Output is correct
5 Correct 72 ms 3660 KB Output is correct
6 Correct 156 ms 3752 KB Output is correct
7 Correct 199 ms 3752 KB Output is correct
8 Correct 162 ms 3788 KB Output is correct
9 Correct 190 ms 3748 KB Output is correct
10 Correct 433 ms 3760 KB Output is correct
11 Correct 402 ms 3752 KB Output is correct
12 Correct 410 ms 3752 KB Output is correct
13 Correct 404 ms 3668 KB Output is correct
14 Correct 406 ms 3768 KB Output is correct
15 Correct 438 ms 3752 KB Output is correct
16 Correct 443 ms 3748 KB Output is correct
17 Correct 412 ms 3668 KB Output is correct
18 Correct 80 ms 3752 KB Output is correct
19 Correct 78 ms 3764 KB Output is correct
20 Correct 88 ms 3668 KB Output is correct
21 Correct 71 ms 3668 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 3752 KB Output is correct
2 Correct 206 ms 3668 KB Output is correct
3 Correct 243 ms 3760 KB Output is correct
4 Correct 195 ms 3720 KB Output is correct
5 Correct 186 ms 3416 KB Output is correct
6 Correct 188 ms 3796 KB Output is correct
7 Correct 223 ms 3880 KB Output is correct
8 Correct 195 ms 3756 KB Output is correct
9 Correct 198 ms 3756 KB Output is correct
10 Correct 439 ms 3788 KB Output is correct
11 Correct 431 ms 3760 KB Output is correct
12 Correct 381 ms 3764 KB Output is correct
13 Correct 375 ms 3756 KB Output is correct
14 Correct 259 ms 3748 KB Output is correct
15 Correct 212 ms 3752 KB Output is correct
16 Correct 246 ms 3760 KB Output is correct
17 Correct 247 ms 3764 KB Output is correct
18 Correct 85 ms 3748 KB Output is correct
19 Correct 87 ms 3752 KB Output is correct
20 Correct 75 ms 3688 KB Output is correct
21 Correct 60 ms 3668 KB Output is correct

Subtask #5
0 / 18.0

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