oj.uz

Submission #656159

# Submission time Handle Problem Language Result Execution time Memory
656159 2022-11-06T12:28:52 Z kinope Bowling (BOI15_bow) C++14
49 / 100
 241 ms 940 KB 
#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

bow.cpp: In function 'void rozw()':
bow.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |   scanf("%d\n", &n);
      |   ~~~~~^~~~~~~~~~~~
bow.cpp:24:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |   for(int i = 1; i <= n; ++i) scanf("%d", &p[i]);
      |                               ~~~~~^~~~~~~~~~~~~
bow.cpp: In function 'int main()':
bow.cpp:92:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |   int q; scanf("%d", &q);
      |          ~~~~~^~~~~~~~~~

Subtask #1
0 / 16.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 852 KB Output is correct
2 Incorrect 82 ms 872 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 852 KB Output is correct
2 Correct 29 ms 852 KB Output is correct
3 Correct 26 ms 852 KB Output is correct
4 Correct 36 ms 852 KB Output is correct
5 Correct 49 ms 856 KB Output is correct
6 Correct 53 ms 856 KB Output is correct
7 Correct 42 ms 852 KB Output is correct
8 Correct 57 ms 852 KB Output is correct
9 Correct 44 ms 852 KB Output is correct
10 Correct 58 ms 940 KB Output is correct
11 Correct 32 ms 816 KB Output is correct
12 Correct 42 ms 816 KB Output is correct
13 Correct 42 ms 872 KB Output is correct
14 Correct 46 ms 852 KB Output is correct
15 Correct 69 ms 824 KB Output is correct
16 Correct 80 ms 856 KB Output is correct
17 Correct 82 ms 860 KB Output is correct
18 Correct 92 ms 868 KB Output is correct
19 Correct 97 ms 852 KB Output is correct
20 Correct 122 ms 852 KB Output is correct
21 Correct 112 ms 852 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 876 KB Output is correct
2 Correct 105 ms 852 KB Output is correct
3 Correct 145 ms 852 KB Output is correct
4 Correct 103 ms 872 KB Output is correct
5 Correct 106 ms 852 KB Output is correct
6 Correct 98 ms 852 KB Output is correct
7 Correct 88 ms 872 KB Output is correct
8 Correct 96 ms 852 KB Output is correct
9 Correct 102 ms 852 KB Output is correct
10 Correct 229 ms 852 KB Output is correct
11 Correct 222 ms 856 KB Output is correct
12 Correct 198 ms 852 KB Output is correct
13 Correct 200 ms 852 KB Output is correct
14 Correct 232 ms 868 KB Output is correct
15 Correct 231 ms 856 KB Output is correct
16 Correct 212 ms 852 KB Output is correct
17 Correct 241 ms 852 KB Output is correct
18 Correct 169 ms 856 KB Output is correct
19 Correct 165 ms 856 KB Output is correct
20 Correct 186 ms 852 KB Output is correct
21 Correct 174 ms 852 KB Output is correct

Subtask #5
0 / 18.0

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