Submission #1128304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128304		Muhammet	Bowling (BOI15_bow)	C++20	26 / 100	2 ms	840 KiB

bow

#include "bits/stdc++.h"

using namespace std;

#define ll long long

ll T, n, dp[55][5005];

string s;

int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> T;
	while(T--){
		cin >> n >> s;
		vector <ll> a(n+1,0);
		for(int i = 1; i <= n; i++){
			cin >> a[i];
		}
		for(int i = 0; i <= 50; i++){
			for(int j = 0; j <= 500; j++){
				dp[i][j] = 0;
			}
		}
		int ind = 0;
		for(int i = 0; i <= 500; i++){
			dp[0][i] = 1;
		}
		for(int i = 1; i < 2*n; i += 2){
			ind++;
			for(int x = (s[i-1] == '?' ? 0 : (s[i-1]-'0')); x <= (s[i-1] == '?' ? 9 : (s[i-1]-'0')); x++){
				for(int y = (s[i] == '?' ? 0 : (s[i]-'0')); y <= (s[i] == '?' ? 9 : (s[i]-'0')); y++){
					if(x + y >= 10) continue;
					if(a[ind] == -1){
						if(a[ind-1] == -1){
							for(int j = 0; j+x+y <= 500; j++){
								dp[ind][j+x+y] += dp[ind-1][j];
							}
						}
						else {
							dp[ind][a[ind-1]+x+y] += dp[ind-1][a[ind-1]];
						}
					}
					else {
						if(a[ind] < x+y) continue;
						if(a[ind-1] == -1){
							dp[ind][a[ind]] += dp[ind-1][a[ind]-(x+y)];
						}
						else {
							if(x + y == (a[ind]-a[ind-1])){
								dp[ind][a[ind]] += dp[ind-1][a[ind-1]];
							}
						}
					}
				}
			}
		}
		ll ans = 0;
		if(a[ind] == -1){
			for(int i = 0; i <= 500; i++){
				ans += dp[ind][i];
			}
		}
		else {
			ans = dp[ind][a[ind]];
		}
		cout << ans << '\n';
	}
}

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