Submission #106607

#	Time	Username	Problem	Language	Result	Execution time	Memory
106607		Bodo171	Bowling (BOI15_bow)	C++14	0 / 100	286 ms	2944 KiB

bow

#include <iostream>
#include <fstream>

using namespace std;
const int nmax=12;
long long dp[nmax][300][12][12];
long long ans;
int val[100];
char ch1,ch2,ch,ch3;
int i,scor,i1,i2,j1,j2,t,n,sum,p1,p2,j,i3;
string s;
bool valid(int x,int y)
{
    ch1=s[2*(i-1)];ch2=s[2*(i-1)+1];
    if(x==10)
    {
        return (((ch1=='x')||(ch1=='?'))&&((ch2=='?'||ch2=='-')));
    }
    if(ch1=='x'||ch2=='-')
    {
        return (x==10);
    }
    bool bun=(ch1=='?'||ch1-'0'==x);
    bun&=(x+y<10);
    if(x+y==10)
    {
        return (bun&&(ch2=='/'||ch2=='?'));
    }
    if(ch2=='/')
    {
        return (((x+y)==10)&&bun);
    }
    bun&=(ch2=='?'||ch2-'0'==y);
    return bun;
}
bool vezi3()
{
    bool bun=1;
    //return (i1==0&&i2==0&&i3==0);
    if(i1+i2<10) bun&=(i3==0);
    if(ch1>='0'&&ch1<='9')
    {
        bun&=(i1==ch1-'0');
    }
    if(ch2>='0'&&ch2<='9')
    {
        bun&=(i2==ch2-'0');
    }
    if(ch3>='0'&&ch3<='9')
    {
        bun&=(i3==ch3-'0');
    }
    return (i1+i2<10);
    if(i1+i2<10) bun&=(ch3=='-'||ch3=='?');
    if(i1==10&&ch2=='/') return 0;
    if(i1==10&&i2+i3==10)
    {
        bun&=((ch3=='?'||ch3=='/'));
    }
    if(ch3=='/')
    {
        bun&=(i1==10&&i2+i3==10);
    }
    if(i1+i2>=10&&ch3=='-') return 0;
    if(i1==10) bun&=(((ch1=='x')||(ch1=='?')));
    if(i1!=10&&i1+i2==10) bun&=(ch2=='/'||ch2=='?');
    return bun;
}
int cl(int i1,int i2,int i3)
{
    int ret=i1+i2+i3;
    if(i1+i2>=10) ret+=i3;
    if(i2==10) ret+=i3;
    return ret;
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>t;
    for(int cnt=1;cnt<=t;cnt++)
    {
        cin>>n;
        cin>>s;
        for(i=1;i<=n;i++)
            cin>>val[i];
        sum=20*n+10;
        ch=s[2*n];
        ch1=s[2*n-2];ch2=s[2*n-1];ch3=s[2*n];
        for(scor=0;scor<=sum;scor++)
        for(i1=0;i1<=10;i1++)
            for(i2=0;i2<=10;i2++)
              for(i3=0;i3<=10;i3++)
                if(vezi3())
        {
            if(scor-cl(i1,i2,i3)>=0&&(val[n]==-1||val[n]==scor)&&(val[n-1]==-1||val[n-1]==scor-cl(i1,i2,i3)))
                {
                   dp[n][scor-cl(i1,i2,i3)][i1][i2]++;
                }
        }
        for(i=n-1;i>=1;i--)
        {
            for(scor=0;scor<=sum;scor++)
                for(i1=0;i1<=10;i1++)
                    for(i2=0;i2<=10-i1;i2++)
                        if(valid(i1,i2))
                   {
                       for(p1=0;p1<=10;p1++)
                         for(p2=0;p2<=10;p2++)
                       {
                            if(i1==10&&scor-10-p1-p2>=0)
                            {
                                dp[i][scor-10-p1-p2][i1][p1]+=dp[i+1][scor][p1][p2];
                            }
                            if(i1!=10&&i1+i2==10&&scor-10-p1>=0)
                            {
                                dp[i][scor-10-p1][i1][i2]+=dp[i+1][scor][p1][p2];
                            }
                            if(i1+i2!=10&&scor-i1-i2>=0)
                            {
                                dp[i][scor-i1-i2][i1][i2]+=dp[i+1][scor][p1][p2];
                            }
                       }
                   }
         if(val[i-1]!=-1)
            for(scor=0;scor<=sum;scor++)
              if(scor!=val[i-1])
               for(i1=0;i1<=10;i1++)
                  for(i2=0;i2<=10;i2++)
                     dp[i][scor][i1][i2]=0;
        }
        ans=0;
        for(i1=0;i1<=10;i1++)
            for(i2=0;i2<=10;i2++)
               ans+=dp[1][0][i1][i2];
        cout<<ans<<'\n';
        for(i=1;i<=n+1;i++)
            for(scor=0;scor<=sum;scor++)
              for(i1=0;i1<=10;i1++)
                for(i2=0;i2<=10;i2++)
                   dp[i][scor][i1][i2]=0;
    }
    return 0;
}

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