oj.uz

Submission #205305

# Submission time Handle Problem Language Result Execution time Memory
205305 2020-02-28T13:37:56 Z TadijaSebez Bowling (BOI15_bow) C++11
42 / 100
 1000 ms 1400 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=11;
const int M=505;
int score[N];
ll dp[M][N][N],tmp[M][N][N];
void Clear(){
	for(int i=0;i<M;i++)
		for(int j=0;j<N;j++)
			for(int k=0;k<N;k++)
				tmp[i][j][k]=dp[i][j][k],dp[i][j][k]=0;
}
void Print(int n){
	for(int i=0;i<M;i++)
		for(int j=0;j<N;j++)
			for(int k=0;k<N;k++)
				if(dp[i][j][k])
					printf("%i %i %i %i %lld\n",n,i,j,k,dp[i][j][k]);
}
void Solve(){
	int n;
	string str;
	scanf("%i",&n);
	cin>>str;
	for(int i=1;i<=n;i++)scanf("%i",&score[i]);
	Clear();
	for(int i=0;i<M;i++)if(i==score[n] || score[n]==-1){
		string now="";now+=str[n*2-2];now+=str[n*2-1];now+=str[n*2];
		//Case 1 xxx
		if((now[0]=='?' || now[0]=='x') && (now[1]=='?' || now[1]=='x') && (now[2]=='?' || now[2]=='x')){
			if(i>=30)dp[i-30][10][10]++;
		}
		//Case 2 xxA
		if((now[0]=='?' || now[0]=='x') && (now[1]=='?' || now[1]=='x')){
			for(int A=0;A<10;A++)if(now[2]=='?' || now[2]=='0'+A){
				if(i>=20+A)dp[i-20-A][10][10]++;
			}
		}
		//Case 3 xA/
		if((now[0]=='?' || now[0]=='x') && (now[2]=='?' || now[2]=='/')){
			for(int A=0;A<10;A++)if(now[1]=='?' || now[1]=='0'+A){
				if(i>=20)dp[i-20][10][A]++;
			}
		}
		//Case 4 xAB
		if(now[0]=='?' || now[0]=='x'){
			for(int A=0;A<10;A++)if(now[1]=='?' || now[1]=='0'+A)
				for(int B=0;B<10;B++)if(A+B<10 && (now[2]=='?' || now[2]=='0'+B)){
					if(i>=10+A+B)dp[i-10-A-B][10][A]++;
				}
		}
		//Case 5 A/x
		if((now[1]=='?' || now[1]=='/') && (now[2]=='?' || now[2]=='x')){
			for(int A=0;A<10;A++)if(now[0]=='?' || now[0]=='0'+A){
				if(i>=20)dp[i-20][A][10-A]++;
			}
		}
		//Case 6 A/B
		if(now[1]=='?' || now[1]=='/'){
			for(int A=0;A<10;A++)if(now[0]=='?' || now[0]=='0'+A)
				for(int B=0;B<10;B++)if(now[2]=='?' || now[2]=='0'+B){
					if(i>=10+B)dp[i-10-B][A][10-A]++;
				}
		}
		//Case 7 AB-
		if(now[2]=='-' || now[2]=='?'){
			for(int A=0;A<10;A++)if(now[0]=='?' || now[0]=='0'+A)
				for(int B=0;B<10;B++)if(A+B<10 && (now[1]=='?' || now[1]=='0'+B)){
					if(i>=A+B)dp[i-A-B][A][B]++;
				}
		}
	}
	//Print(n);
	for(int j=n-1;j>=1;j--){
		Clear();
		string now="";now+=str[j*2-2];now+=str[j*2-1];
		for(int i=0;i<M;i++)if(score[j]==i || score[j]==-1){
			for(int F=0;F<N;F++)for(int S=0;S<N;S++){
				//Case 1 x-
				if((now[0]=='?' || now[0]=='x') && (now[1]=='?' || now[1]=='-')){
					if(i>=10+F+S)dp[i-10-F-S][10][F]+=tmp[i][F][S];
				}
				//Case 2 A/
				if(now[1]=='?' || now[1]=='/'){
					for(int A=0;A<10;A++)if(now[0]=='?' || now[0]=='0'+A){
						if(i>=10+F)dp[i-10-F][A][10-A]+=tmp[i][F][S];
					}
				}
				//Case 3 AB
				for(int A=0;A<10;A++)if(now[0]=='?' || now[0]=='0'+A)
					for(int B=0;B<10;B++)if(A+B<10 && (now[1]=='?' || now[1]=='0'+B)){
						if(i>=A+B)dp[i-A-B][A][B]+=tmp[i][F][S];
					}
			}
		}
		//Print(j);
	}
	ll ans=0;
	for(int F=0;F<N;F++)for(int S=0;S<N;S++)ans+=dp[0][F][S];
	printf("%lld\n",ans);
}
int main(){
	int t;scanf("%i",&t);
	while(t--)Solve();
	return 0;
}

Compilation message

bow.cpp: In function 'void Solve()':
bow.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
bow.cpp:26:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++)scanf("%i",&score[i]);
                       ~~~~~^~~~~~~~~~~~~~~~
bow.cpp: In function 'int main()':
bow.cpp:104:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int t;scanf("%i",&t);
        ~~~~~^~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 1272 KB Output is correct
2 Correct 207 ms 1276 KB Output is correct
3 Correct 15 ms 1272 KB Output is correct
4 Correct 16 ms 1272 KB Output is correct
5 Correct 16 ms 1272 KB Output is correct
6 Correct 17 ms 1272 KB Output is correct
7 Correct 526 ms 1272 KB Output is correct
8 Correct 509 ms 1272 KB Output is correct
9 Correct 501 ms 1268 KB Output is correct
10 Correct 511 ms 1272 KB Output is correct
11 Correct 569 ms 1144 KB Output is correct
12 Correct 269 ms 1272 KB Output is correct
13 Correct 57 ms 1272 KB Output is correct
14 Correct 267 ms 1272 KB Output is correct
15 Correct 70 ms 1272 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 582 ms 1272 KB Output is correct
2 Correct 518 ms 1272 KB Output is correct
3 Correct 435 ms 1272 KB Output is correct
4 Correct 385 ms 1272 KB Output is correct
5 Correct 495 ms 1400 KB Output is correct
6 Correct 616 ms 1272 KB Output is correct
7 Correct 674 ms 1272 KB Output is correct
8 Correct 643 ms 1272 KB Output is correct
9 Correct 596 ms 1272 KB Output is correct
10 Execution timed out 1087 ms 1144 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 1272 KB Output is correct
2 Correct 116 ms 1272 KB Output is correct
3 Correct 128 ms 1272 KB Output is correct
4 Correct 149 ms 1272 KB Output is correct
5 Correct 234 ms 1272 KB Output is correct
6 Correct 244 ms 1272 KB Output is correct
7 Correct 191 ms 1272 KB Output is correct
8 Correct 250 ms 1276 KB Output is correct
9 Correct 171 ms 1272 KB Output is correct
10 Correct 187 ms 1272 KB Output is correct
11 Correct 100 ms 1272 KB Output is correct
12 Correct 110 ms 1272 KB Output is correct
13 Correct 122 ms 1272 KB Output is correct
14 Correct 258 ms 1272 KB Output is correct
15 Correct 316 ms 1272 KB Output is correct
16 Correct 313 ms 1272 KB Output is correct
17 Correct 354 ms 1272 KB Output is correct
18 Correct 225 ms 1272 KB Output is correct
19 Correct 280 ms 1272 KB Output is correct
20 Correct 301 ms 1272 KB Output is correct
21 Correct 318 ms 1272 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 707 ms 1272 KB Output is correct
2 Correct 588 ms 1272 KB Output is correct
3 Correct 732 ms 1272 KB Output is correct
4 Correct 580 ms 1272 KB Output is correct
5 Correct 562 ms 1272 KB Output is correct
6 Correct 460 ms 1272 KB Output is correct
7 Correct 503 ms 1272 KB Output is correct
8 Correct 479 ms 1272 KB Output is correct
9 Correct 513 ms 1272 KB Output is correct
10 Execution timed out 1092 ms 1272 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 1272 KB Output is correct
2 Correct 207 ms 1276 KB Output is correct
3 Correct 15 ms 1272 KB Output is correct
4 Correct 16 ms 1272 KB Output is correct
5 Correct 16 ms 1272 KB Output is correct
6 Correct 17 ms 1272 KB Output is correct
7 Correct 526 ms 1272 KB Output is correct
8 Correct 509 ms 1272 KB Output is correct
9 Correct 501 ms 1268 KB Output is correct
10 Correct 511 ms 1272 KB Output is correct
11 Correct 569 ms 1144 KB Output is correct
12 Correct 269 ms 1272 KB Output is correct
13 Correct 57 ms 1272 KB Output is correct
14 Correct 267 ms 1272 KB Output is correct
15 Correct 70 ms 1272 KB Output is correct
16 Correct 582 ms 1272 KB Output is correct
17 Correct 518 ms 1272 KB Output is correct
18 Correct 435 ms 1272 KB Output is correct
19 Correct 385 ms 1272 KB Output is correct
20 Correct 495 ms 1400 KB Output is correct
21 Correct 616 ms 1272 KB Output is correct
22 Correct 674 ms 1272 KB Output is correct
23 Correct 643 ms 1272 KB Output is correct
24 Correct 596 ms 1272 KB Output is correct
25 Execution timed out 1087 ms 1144 KB Time limit exceeded
26 Halted 0 ms 0 KB -