# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
656159 | kinope | Bowling (BOI15_bow) | C++14 | 241 ms | 940 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[301][11][11], dp2[301][11][11];
int p[11];
void Clear(){
for(int i = 0; i < 301; ++i)
for(int j = 0; j < 11; ++j)
for(int k = 0; k < 11; ++k) dp2[i][j][k]=0, dp[i][j][k]=0;
}
void Copy(){
for(int i = 0; i < 301; ++i)
for(int j = 0; j < 11; ++j)
for(int k = 0; k < 11; ++k) dp2[i][j][k]=dp[i][j][k], dp[i][j][k]=0;
}
void rozw(){
int n; string s; char c;
scanf("%d\n", &n);
for(int i = 0; i <= n<<1; ++i) c = getchar_unlocked(), s+=c;
//cin >> s;
for(int i = 1; i <= n; ++i) scanf("%d", &p[i]);
Clear();
//runda specjalna
for(int pkt = 300; ~pkt; --pkt) if(pkt==p[n]||p[n]==-1){
char t[3] = {s[n*2-2], s[n*2-1], s[n*2]};
//xxx
if(pkt-30>0) if((t[0]=='x'||t[0]=='?') && (t[1]=='x'||t[1]=='?') && (t[2]=='x'||t[2]=='?')) ++dp[pkt-30][10][10];
//xxA
for(int A = 0; A < 10; ++A) if(pkt-20-A>=0)
if((t[0]=='x'||t[0]=='?') && (t[1]=='x'||t[1]=='?') && (t[2]=='0'+A||t[2]=='?')) ++dp[pkt-20-A][10][10];
//xA/
for(int A = 0; A < 10; ++A) if(pkt-20>=0)
if((t[0]=='x'||t[0]=='?') && (t[1]=='0'+A||t[1]=='?') && (t[2]=='/'||t[2]=='?')) ++dp[pkt-20][10][A];
//xAB
for(int A = 0; A < 10; ++A)
for(int B = 0; B < 10; ++B) if(pkt-10-A-B>=0)
if((t[0]=='x'||t[0]=='?') && (t[1]=='0'+A||t[1]=='?') && (t[2]=='0'+B||t[2]=='?')) ++dp[pkt-10-A-B][10][A];
//A/x
for(int A = 0; A < 10; ++A) if(pkt-20>=0)
if((t[0]=='0'+A||t[0]=='?') && (t[1]=='/'||t[1]=='?') && (t[2]=='x'||t[2]=='?')) ++dp[pkt-20][A][10-A];
//A/B
for(int A = 0; A < 10; ++A)
for(int B = 0; B < 10; ++B) if(pkt-10-B>=0)
if((t[0]=='0'+A||t[0]=='?') && (t[1]=='/'||t[1]=='?') && (t[2]=='0'+B||t[2]=='?')) ++dp[pkt-10-B][A][10-A];
//AB-
for(int A = 0; A < 10; ++A)
for(int B = 0; B < 10-A; ++B) if(pkt-A-B>=0)
if((t[0]=='0'+A||t[0]=='?') && (t[1]=='0'+B||t[1]=='?') && (t[2]=='-'||t[2]=='?')) {++dp[pkt-A-B][A][B];}
}
for(--n; n; --n){
Copy();
for(int pkt = n*30; ~pkt; --pkt) if(pkt==p[n]||p[n]==-1){
char t[2] = {s[n*2-2], s[n*2-1]};
//x-
for(int A = 0; A <= 10; ++A)
for(int B = 0; B <= 10; ++B) if(pkt-10-A-B>=0)
if((t[0]=='x'||t[0]=='?') && (t[1]=='-'||t[1]=='?')) dp[pkt-10-A-B][10][A] += dp2[pkt][A][B];
//A/
for(int A = 0; A < 10; ++A)
for(int B = 0; B <= 10; ++B) if(pkt-10-B>=0)
for(int C = 0; C <= 10; ++C)
if((t[0]=='0'+A||t[0]=='?') && (t[1]=='/'||t[1]=='?')) dp[pkt-10-B][A][10-A] += dp2[pkt][B][C];
//AB
for(int A = 0; A < 10; ++A)
for(int B = 0; B < 10-A; ++B) if(pkt-A-B>=0)
for(int C = 0; C <= 10; ++C) for(int D = 0; D <= 10; ++D)
if((t[0]=='0'+A||t[0]=='?') && (t[1]=='0'+B||t[1]=='?')) dp[pkt-A-B][A][B] += dp2[pkt][C][D];
}
}
ll wynik = 0;
for(int A = 0; A <= 10; ++A)
for(int B = 0; B <= 10; ++B) wynik += dp[0][A][B];
printf("%lld\n", wynik);
}
int main(){
int q; scanf("%d", &q);
for(++q; --q; ) rozw();
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |