Submission #134782

#	Time	Username	Problem	Language	Result	Execution time	Memory
134782		faustaadp	Bowling (BOI15_bow)	C++17	59 / 100	1071 ms	3740 KiB

bow

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll t,n,sl,has,d[11][310][11][11],x[1010],i,a[1010][3];
string s;
ll con(char aa)
{
	if('0'<=aa&&aa<='9')
		return (aa-'0');
	if(aa=='-')
		return 12;
	if(aa=='x')
		return 10;
	if(aa=='/')
		return 11;
	if(aa=='?')
		return -1;
}
void ubah()
{
	ll ii,jj;
	for(ii=1;ii<=n;ii++)
		for(jj=1;jj<=2;jj++)
		{
			a[ii][jj]=con(s[(ii-1)*2+(jj-1)]);
		}
	a[n][3]=con(s[sl-1]);
}
ll depe(ll aa,ll bb,ll cc,ll dd)
{
	if(aa==0&&bb==0)return 1;
	if(aa==0||bb<0)return 0;
	if(x[aa]!=-1&&x[aa]!=bb)return 0;
	if(d[aa][bb][cc][dd]==-1)
	{
		d[aa][bb][cc][dd]=0;
		if(aa==n)
		{
			ll ii,jj;
			if((a[aa][1]==10||a[aa][1]==-1)&&(a[aa][2]==10||a[aa][2]==-1)&&(a[aa][3]==10||a[aa][3]==-1))
				d[aa][bb][cc][dd]+=depe(aa-1,bb-30,10,10);
			for(ii=0;ii<=9;ii++)
			{
				if((a[aa][1]==10||a[aa][1]==-1)&&(a[aa][2]==10||a[aa][2]==-1)&&(a[aa][3]==ii||a[aa][3]==-1))
					d[aa][bb][cc][dd]+=depe(aa-1,bb-(20+ii),10,10);
				if((a[aa][1]==10||a[aa][1]==-1)&&(a[aa][2]==ii||a[aa][2]==-1)&&(a[aa][3]==11||a[aa][3]==-1))
					d[aa][bb][cc][dd]+=depe(aa-1,bb-20,10,ii);
				if((a[aa][1]==ii||a[aa][1]==-1)&&(a[aa][2]==11||a[aa][2]==-1)&&(a[aa][3]==10||a[aa][3]==-1))
					d[aa][bb][cc][dd]+=depe(aa-1,bb-20,ii,10-ii);
				for(jj=0;jj<=9;jj++)
				{
					if((a[aa][1]==ii||a[aa][1]==-1)&&(a[aa][2]==11||a[aa][2]==-1)&&(a[aa][3]==jj||a[aa][3]==-1))
						d[aa][bb][cc][dd]+=depe(aa-1,bb-(10+jj),ii,10-ii);
					if((ii+jj)<10)
					{
						if((a[aa][1]==10||a[aa][1]==-1)&&(a[aa][2]==ii||a[aa][2]==-1)&&(a[aa][3]==jj||a[aa][3]==-1))
							d[aa][bb][cc][dd]+=depe(aa-1,bb-(10+ii+jj),10,ii);
						if((a[aa][1]==ii||a[aa][1]==-1)&&(a[aa][2]==jj||a[aa][2]==-1)&&(a[aa][3]==12||a[aa][3]==-1))
							d[aa][bb][cc][dd]+=depe(aa-1,bb-(ii+jj),ii,jj);
					}
				}
			}
		}
		else
		{	
			ll ii,jj;
			for(ii=0;ii<=9;ii++)
				for(jj=0;jj<=9;jj++)
					if((ii+jj)<10)
					{
						if((a[aa][1]==ii||a[aa][1]==-1)&&(a[aa][2]==jj||a[aa][2]==-1))
						{
							d[aa][bb][cc][dd]+=depe(aa-1,bb-(ii+jj),ii,jj);
						}
					}
			if((a[aa][1]==10||a[aa][1]==-1)&&(a[aa][2]==12||a[aa][2]==-1))
			{
				d[aa][bb][cc][dd]+=depe(aa-1,bb-(10+cc+dd),10,cc);
			}
			for(ii=0;ii<=9;ii++)
			{
				if((a[aa][1]==ii||a[aa][1]==-1)&&(a[aa][2]==11||a[aa][2]==-1))
				{
					d[aa][bb][cc][dd]+=depe(aa-1,bb-(10+cc),ii,10-ii);
				}
			}
		}
	}
	return d[aa][bb][cc][dd];
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>t;
	while(t--)
	{
		has=0;
		cin>>n;
		cin>>s;
		sl=s.length();
		for(i=1;i<=n;i++)
			cin>>x[i];
		ubah();
		memset(d,-1,sizeof(d));
		has=0;
		for(i=0;i<=300;i++)
			has+=depe(n,i,0,0);
		cout<<has<<"\n";
	}
}

Compilation message (stderr)

bow.cpp: In function 'll con(char)':
bow.cpp:22:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
bow.cpp: In function 'void ubah()':
bow.cpp:31:8: warning: array subscript is above array bounds [-Warray-bounds]
  a[n][3]=con(s[sl-1]);
  ~~~~~~^
bow.cpp: In function 'll depe(ll, ll, ll, ll)':
bow.cpp:44:75: warning: array subscript is above array bounds [-Warray-bounds]
    if((a[aa][1]==10||a[aa][1]==-1)&&(a[aa][2]==10||a[aa][2]==-1)&&(a[aa][3]==10||a[aa][3]==-1))
                                                                    ~~~~~~~^
bow.cpp:48:76: warning: array subscript is above array bounds [-Warray-bounds]
     if((a[aa][1]==10||a[aa][1]==-1)&&(a[aa][2]==10||a[aa][2]==-1)&&(a[aa][3]==ii||a[aa][3]==-1))
                                                                     ~~~~~~~^
bow.cpp:50:76: warning: array subscript is above array bounds [-Warray-bounds]
     if((a[aa][1]==10||a[aa][1]==-1)&&(a[aa][2]==ii||a[aa][2]==-1)&&(a[aa][3]==11||a[aa][3]==-1))
                                                                     ~~~~~~~^
bow.cpp:52:76: warning: array subscript is above array bounds [-Warray-bounds]
     if((a[aa][1]==ii||a[aa][1]==-1)&&(a[aa][2]==11||a[aa][2]==-1)&&(a[aa][3]==10||a[aa][3]==-1))
                                                                     ~~~~~~~^
bow.cpp:56:77: warning: array subscript is above array bounds [-Warray-bounds]
      if((a[aa][1]==ii||a[aa][1]==-1)&&(a[aa][2]==11||a[aa][2]==-1)&&(a[aa][3]==jj||a[aa][3]==-1))
                                                                      ~~~~~~~^
bow.cpp:60:78: warning: array subscript is above array bounds [-Warray-bounds]
       if((a[aa][1]==10||a[aa][1]==-1)&&(a[aa][2]==ii||a[aa][2]==-1)&&(a[aa][3]==jj||a[aa][3]==-1))
                                                                       ~~~~~~~^
bow.cpp:62:78: warning: array subscript is above array bounds [-Warray-bounds]
       if((a[aa][1]==ii||a[aa][1]==-1)&&(a[aa][2]==jj||a[aa][2]==-1)&&(a[aa][3]==12||a[aa][3]==-1))
                                                                       ~~~~~~~^

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