Submission #230111

#	Time	Username	Problem	Language	Result	Execution time	Memory
230111		Kastanda	Bowling (BOI15_bow)	C++11	100 / 100	117 ms	3456 KiB

bow

// Pinkie Pied!
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 11;
int n, A[N];
ll dp[N][N][N][279];
char S[N * 2];
int main()
{
    int q;
    scanf("%d", &q);
    for (; q; q --)
    {
        memset(S, 0, sizeof(S));
        memset(A, 0, sizeof(A));
        scanf("%d%s", &n, S);
        for (int i = 1; i <= n; i ++)
            scanf("%d", &A[i]);
        memset(dp, 0, sizeof(dp));
        for (int a = 0; a < 10; a ++)
            for (int b = 0; a + b <= 10; b ++)
                dp[0][a][b][0] = 1;
        for (int b = 0; b <= 10; b ++)
            dp[0][10][b][0] = 1;
        A[0] = -1;
        ll tot = 0;
        for (int i = 0; i <= n - 2; i ++)
        {
            int le = 0, ri = 30 * i;
            if (A[i] != -1)
                le = A[i], ri = A[i];
            for (int a = 0; a < 10; a ++)
                for (int b = 0; a + b < 10; b ++)
                {
                    if (S[i * 2] != '?' && S[i * 2] != '0' + a)
                        continue;
                    if (S[i * 2 + 1] != '?' && S[i * 2 + 1] != '0' + b)
                        continue;
                    for (int c = 0; c <= 10; c ++)
                        for (int d = 0; d <= 10 && (c == 10 || c + d <= 10); d ++)
                            for (int j = le; j <= ri; j ++)
                                dp[i + 1][c][d][j + a + b] += dp[i][a][b][j];
                }
            for (int a = 0; a < 10; a ++)
            {
                int b = 10 - a;
                if (S[i * 2] != '?' && S[i * 2] != '0' + a)
                    continue;
                if (S[i * 2 + 1] != '?' && S[i * 2 + 1] != '/')
                    continue;
                for (int c = 0; c <= 10; c ++)
                    for (int d = 0; d <= 10 && (c == 10 || c + d <= 10); d ++)
                        for (int j = le; j <= ri; j ++)
                            dp[i + 1][c][d][j + 10 + c] += dp[i][a][b][j];
            }
            if (S[i * 2] != '?' && S[i * 2] != 'x')
                continue;
            if (S[i * 2 + 1] != '?' && S[i * 2 + 1] != '-')
                continue;
            int a = 10;
            for (int c = 0; c <= 10; c ++)
                for (int d = 0; d <= 10 && (c == 10 || c + d <= 10); d ++)
                    for (int j = le; j <= ri; j ++)
                        dp[i + 1][c][d][j + 10 + c + d] += dp[i][a][c][j];
        }
        for (int i = n - 1; i <= n - 1; i ++)
        {
            int le = 0, ri = 30 * i;
            if (A[i] != -1)
                le = A[i], ri = A[i];
            for (int a = 0; a < 10; a ++)
                for (int b = 0; a + b < 10; b ++)
                {
                    if (S[i * 2] != '?' && S[i * 2] != '0' + a)
                        continue;
                    if (S[i * 2 + 1] != '?' && S[i * 2 + 1] != '0' + b)
                        continue;
                    if (S[i * 2 + 2] != '?' && S[i * 2 + 2] != '-')
                        continue;
                    for (int j = le; j <= ri; j ++)
                        if (A[i + 1] == -1 || j + a + b == A[i + 1])
                            tot += dp[i][a][b][j];
                }
            for (int a = 0; a < 10; a ++)
            {
                int b = 10 - a;
                if (S[i * 2] != '?' && S[i * 2] != '0' + a)
                    continue;
                if (S[i * 2 + 1] != '?' && S[i * 2 + 1] != '/')
                    continue;

                if (S[i * 2 + 2] == '?' || S[i * 2 + 2] == 'x')
                    for (int j = le; j <= ri; j ++)
                        if (A[i + 1] == -1 || j + a + b + 10 == A[i + 1])
                            tot += dp[i][a][b][j];
                for (int c = 0; c < 10; c ++)
                    if (S[i * 2 + 2] == '?' || S[i * 2 + 2] - '0' == c)
                        for (int j = le; j <= ri; j ++)
                            if (A[i + 1] == -1 || j + a + b + c == A[i + 1])
                                tot += dp[i][a][b][j];
            }
            if (S[i * 2] != '?' && S[i * 2] != 'x')
                continue;
            int a = 10;
            for (int b = 0; b < 10; b ++)
            {
                if (S[i * 2 + 1] != '?' && S[i * 2 + 1] != '0' + b)
                    continue;
                for (int c = 0; b + c < 10; c ++)
                {
                    if (S[i * 2 + 2] != '?' && S[i * 2 + 2] != '0' + c)
                        continue;
                    for (int j = le; j <= ri; j ++)
                        if (A[i + 1] == -1 || j + 10 + b + c == A[i + 1])
                            tot += dp[i][a][b][j];
                }
                if (S[i * 2 + 2] != '?' && S[i * 2 + 2] != '/')
                    continue;
                int c = 10 - b;
                for (int j = le; j <= ri; j ++)
                    if (A[i + 1] == -1 || j + 10 + b + c == A[i + 1])
                        tot += dp[i][a][b][j];
            }
            if (S[i * 2 + 1] != '?' && S[i * 2 + 1] != 'x')
                continue;
            int b = 10;
            for (int c = 0; c < 10; c ++)
            {
                if (S[i * 2 + 2] != '?' && S[i * 2 + 2] != '0' + c)
                    continue;
                for (int j = le; j <= ri; j ++)
                    if (A[i + 1] == -1 || j + 10 + b + c == A[i + 1])
                        tot += dp[i][a][b][j];
            }
            if (S[i * 2 + 2] != '?' && S[i * 2 + 2] != 'x')
                continue;
            int c = 10;
            for (int j = le; j <= ri; j ++)
                if (A[i + 1] == -1 || j + 10 + b + c == A[i + 1])
                    tot += dp[i][a][b][j];
        }
        printf("%lld\n", tot);
    }
    return 0;
}

Compilation message (stderr)

bow.cpp: In function 'int main()':
bow.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
bow.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%s", &n, S);
         ~~~~~^~~~~~~~~~~~~~~
bow.cpp:19:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &A[i]);
             ~~~~~^~~~~~~~~~~~~

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