Submission #151215

#	Time	Username	Problem	Language	Result	Execution time	Memory
151215		Charis02	Bowling (BOI15_bow)	C++14	26 / 100	7 ms	888 KiB

bow

#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 12
#define MAXSCORE 300
#define INF 1e9+7

using namespace std;

ll q,n;
ll dp[N][MAXSCORE][3],ar[N]; // 0 -> normal , 1 -> spare , 2-> strike
string s;

ll calculate(ll round,ll score,ll type)
{
    char p1 = s[2*(round-1)];
    char p2 = s[2*(round-1)+1];

    ll res = 0;

    if(p1 == 'x')
    {
        if(type == 2)
        {

        }
        else
            return 0;
    }
    else if(p2 == '/')
    {
        if(type == 1)
        {

        }
        else
            return 0;
    }
    else if(p1 == '?' && p2 == '?')
    {
        if(type == 0)
        {
            rep(a,0,10)
            {
                rep(b,0,10)
                {
                    if(a+b >= 10 || a+b > score)
                        break;

                    res += dp[round-1][score-a-b][0];

                    if(2*a+b > score)
                        continue;

                    res += dp[round-1][score-2*a-b][1];

                    if(2*a+2*b > score)
                        continue;

                    res += dp[round-1][score-2*a-2*b][2];
                }
            }
        }
        else if(type == 1)
        {

        }
        else if(type == 2)
        {

        }
    }
    else if(p1 == '?')
    {
        if(type == 0)
        {
            ll b = p2-'0';

            rep(a,0,10)
            {
                if(a+b >= 10 || a+b > score)
                    break;

                res += dp[round-1][score-a-b][0];

                if(2*a+b > score)
                    continue;

                res += dp[round-1][score-2*a-b][1];

                if(2*a+2*b > score)
                    continue;

                res += dp[round-1][score-2*a-2*b][2];
            }

            return res;
        }
        else if(type == 1)
        {
            return 0;
        }
        else
            return 0;
    }
    else if(p2 == '?')
    {
        if(type == 0)
        {
            ll a = p1-'0';

            rep(b,0,10)
            {
                if(a+b >= 10 || a+b > score)
                    break;

                res += dp[round-1][score-a-b][0];

                if(2*a+b > score)
                    continue;

                res += dp[round-1][score-2*a-b][1];

                if(2*a+2*b > score)
                    continue;

                res += dp[round-1][score-2*a-2*b][2];
            }

            return res;
        }
        else if(type == 1)
        {

        }
        else
            return 0;
    }
    else
    {
        if(type == 0)
        {
            ll a = p1-'0';
            ll b = p2 - '0';

            if(a+b < 10 && a+b<=score)
                res += dp[round-1][score-a-b][0];

            if(2*a+b <= score)
                res += dp[round-1][score-2*a-b][1];

            if(2*a+2*b <= score)
                res += dp[round-1][score-2*a-2*b][2];

            return res;
        }
        else
        {
            return 0;
        }
    }

    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);

    cin >> q;

    while(q--)
    {
        cin >> n;

        cin >> s;

        rep(i,0,s.size()-3)
        {
            if(s[i] == '-')
                s[i-1] = 'x';

            if(s[i] == 'x')
                s[i-1] = '-';
        }

        rep(i,1,n+1)
        {
            cin >> ar[i];
        }

        memset(dp,0,sizeof dp);
        dp[0][0][0] = 1;

        rep(i,1,n)
        {
            rep(j,0,MAXSCORE)
            {
                rep(k,0,3)
                {
                    if(ar[i] == -1 || ar[i] == j)
                        dp[i][j][k] = calculate(i,j,k);
                    else
                        dp[i][j][k] = 0;
                }
            }

    //        ll x;
         //   cin >> x;
     //       cout << dp[i][ar[i]][0] << " ";
        }

     //   cout << endl;
        ll ans = 0;

        if(ar[n] == -1)
        {
            rep(j,0,MAXSCORE)
                ans += calculate(n,j,0)+calculate(n,j,1)+calculate(n,j,2);
        }
        else
        {
            ans = calculate(n,ar[n],0)+calculate(n,ar[n],1)+calculate(n,ar[n],2);
        }

        cout << ans << "\n";
    }

    return 0;
}

Compilation message (stderr)

bow.cpp: In function 'int main()':
bow.cpp:13:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
bow.cpp:188:13:
         rep(i,0,s.size()-3)
             ~~~~~~~~~~~~~~          
bow.cpp:188:9: note: in expansion of macro 'rep'
         rep(i,0,s.size()-3)
         ^~~

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