Submission #656189

#	Time	Username	Problem	Language	Result	Execution time	Memory
656189		kinope	Bowling (BOI15_bow)	C++14	100 / 100	577 ms	972 KiB

bow

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[302][11][11], dp2[302][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();
		for(int pkt = 301; ~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-A; ++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)

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:91:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |   int q; scanf("%d", &q);
      |          ~~~~~^~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 17 / 17
• Subtask 3: 26 / 26
• Subtask 4: 23 / 23
• Subtask 5: 18 / 18