Submission #725463

#TimeUsernameProblemLanguageResultExecution timeMemory
725463berrBowling (BOI15_bow)C++17
49 / 100
679 ms3880 KiB
#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 (stderr)

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;
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...