oj.uz

Submission #923523

# Submission time Handle Problem Language Result Execution time Memory
923523 2024-02-07T11:32:21 Z andrei_iorgulescu Bowling (BOI15_bow) C++14
39 / 100
 1000 ms 110680 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

int dp[11][301][11][11][32];
int sdp[11][301][31][11],sumdp[11][301][31];
int n;
char a[25];
int v[15];

bool ok(int x,int pos,bool strike,int prec)
{
    if (a[pos] == '?')
        return true;
    char cx;
    if (x == -1)
        cx = '-';
    else if (prec == -1)
    {
        if (x >= 0 and x <= 9)
            cx = (char)('0' + x);
        else
            cx = 'x';
    }
    else
    {
        if (x + prec < 10)
            cx = (char)('0' + x);
        else
            cx = '/';
    }
    if (cx == a[pos])
        return true;
    return false;
}

bool okv(int x,int pos)
{
    if (v[pos] == -1)
        return true;
    if (x == v[pos])
        return true;
    return false;
}

int f(int c11,int c12,int c21,int c22)
{
    if (c11 == 10)
    {
        if (c12 != c21)
            return 31;
        return 10 + c21 + c22;
    }
    if (c11 + c12 < 10)
        return c11 + c12;
    else if (c11 + c12 > 10)
        return 31;
    return 10 + c21;
}

void testcase()
{
    for (int i = 0; i < 11; i++)
        for (int j = 0; j < 301; j++)
            for (int ii = 0; ii < 11; ii++)
                for (int jj = 0; jj < 11; jj++)
                    for (int kkk = 0; kkk < 32; kkk++)
                        dp[i][j][ii][jj][kkk] = 0;
    for (int i = 0; i < 11; i++)
        for (int j = 0; j < 301; j++)
            for (int ii = 0; ii < 31; ii++)
                for (int jj = 0; jj < 11; jj++)
                    sdp[i][j][ii][jj] = 0;
    for (int i = 0; i < 11; i++)
        for (int j = 0; j < 301; j++)
            for (int ii = 0; ii < 31; ii++)
                sumdp[i][j][ii] = 0;
    cin >> n;
    for (int i = 1; i <= 2 * n + 1; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> v[i];
    for (int s = 0; s <= 30 * n; s++)
    {
        for (int h1 = 0; h1 <= 10; h1++)
        {
            if (h1 == 10)
            {
                for (int h2 = 0; h2 <= 10; h2++)
                {
                    if (h2 == 10)
                    {
                        for (int h3 = 0; h3 <= 10; h3++)
                        {
                            if (h1 + h2 + h3 <= s and ok(h1,2 * n - 1,true,-1) and ok(h2,2 * n,true,-1) and ok(h3,2 * n + 1,true,-1) and okv(s,n))
                                dp[n][s][h1][h2][h1 + h2 + h3]++;
                        }
                    }
                    else
                    {
                        for (int h3 = 0; h3 <= 10 - h2; h3++)
                        {
                            if (h1 + h2 + h3 <= s and ok(h1,2 * n - 1,true,-1) and ok(h2,2 * n,false,-1) and ok(h3,2 * n + 1,false,h2) and okv(s,n))
                                dp[n][s][h1][h2][h1 + h2 + h3]++;
                        }
                    }
                }
            }
            else
            {
                for (int h2 = 0; h2 <= 10 - h1; h2++)
                {
                    if (h1 + h2 == 10 and ok(h1,2 * n - 1,false,-1) and ok(h2, 2 * n,false,h1))
                    {
                        for (int h3 = 0; h3 <= 10; h3++)
                        {
                            if (ok(h3,2 * n + 1,true,-1) and h1 + h2 + h3 <= s and okv(s,n))
                                dp[n][s][h1][h2][h1 + h2 + h3]++;
                        }
                    }
                    else if (h1 + h2 < 10)
                    {
                        if (h1 + h2 <= s and ok(h1,2 * n - 1,false,-1) and ok(h2,2 * n,false,h1) and ok(-1,2 * n + 1,false,-1) and okv(s,n))
                            dp[n][s][h1][h2][h1 + h2]++;
                    }
                }
            }
        }
    }
    /*for (int i = n; i > 1; i--)
    {
        for (int s = 0; s <= 30 * i; s++)
        {
            for (int h1 = 0; h1 <= 10; h1++)
            {
                for (int h2 = 0; h2 <= 10; h2++)
                {
                    for (int vl = 0; vl <= min(30ll,s); vl++)
                    {
                        if (dp[i][s][h1][h2][vl] == 0)
                            continue;
                        if (!okv(s - vl,i - 1))
                            continue;
                        //cout << i << ' ' << s << ' ' << h1 << ' ' << h2 << ' ' << vl << endl;
                        for (int h1p = 0; h1p <= 10; h1p++)
                        {
                            for (int h2p = 0; h2p <= 10; h2p++)
                            {
                                if (f(h1p,h2p,h1,h2) <= s - vl)
                                {
                                    if (h1p == 10 and ok(10,2 * i - 3,true,-1) and ok(-1,2 * i - 2,false,-1))
                                        dp[i - 1][s - vl][h1p][h2p][f(h1p,h2p,h1,h2)] += dp[i][s][h1][h2][vl];
                                    else if (h1p != 10)
                                    {
                                        if (h1p + h2p <= 10 and ok(h1p,2 * i - 3,false,-1) and ok(h2p,2 * i - 2,false,h1p))
                                            dp[i - 1][s - vl][h1p][h2p][f(h1p,h2p,h1,h2)] += dp[i][s][h1][h2][vl];
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }*/
    for (int s = 0; s <= 30 * n; s++)
    {
        for (int h1 = 0; h1 <= 10; h1++)
        {
            for (int h2 = 0; h2 <= 10; h2++)
            {
                for (int vl = 0; vl <= 30; vl++)
                {
                    sumdp[n][s][vl] += dp[n][s][h1][h2][vl];
                    sdp[n][s][vl][h1] += dp[n][s][h1][h2][vl];
                    //if (dp[n][s][h1][h2][vl] != 0)
                      //  cout << s << ' ' << h1 << ' ' << h2 << ' ' << vl << ' ' << dp[n][s][h1][h2][vl] << endl;
                }
            }
        }
    }
    for (int i = n - 1; i >= 1; i--)
    {
        for (int s = 0; s <= 30 * i; s++)
        {
            for (int h1 = 0; h1 <= 10; h1++)
            {
                for (int h2 = 0; h2 <= 10; h2++)
                {
                    for (int vlp = 0; vlp <= 30; vlp++)
                    {
                        if (h1 == 10)
                        {
                            for (int h2p = 0; h2p <= 10; h2p++)
                                if (ok(h1,2 * i - 1,true,-1) and ok(-1,2 * i,true,-1))
                                    dp[i][s][h1][h2][10 + h2 + h2p] += dp[i + 1][s + vlp][h2][h2p][vlp];
                        }
                        else if (h1 + h2 == 10)
                        {
                            for (int h1p = 0; h1p <= 10; h1p++)
                                if (ok(h1,2 * i - 1,false,-1) and ok(h2,2 * i,false,h1))
                                    dp[i][s][h1][h2][10 + h1p] += sdp[i + 1][s + vlp][vlp][h1p];
                        }
                        else if (h1 + h2 < 10)
                        {
                            if (ok(h1,2 * i - 1,false,-1) and ok(h2,2 * i,false,h1))
                                dp[i][s][h1][h2][h1 + h2] += sumdp[i + 1][s + vlp][vlp];
                        }
                    }
                }
            }
        }
        for (int s = 0; s <= 30 * i; s++)
        {
            for (int h1 = 0; h1 <= 10; h1++)
            {
                for (int h2 = 0; h2 <= 10; h2++)
                {
                    for (int vl = 0; vl <= 30; vl++)
                    {
                        if (!okv(s,i))
                            dp[i][s][h1][h2][vl] = 0;
                        //if (dp[i][s][h1][h2][vl] != 0)
                          //  cout << i << ' ' << s << ' ' << h1 << ' ' << h2 << ' ' << vl << ' ' << dp[i][s][h1][h2][vl] << endl;
                        sumdp[i][s][vl] += dp[i][s][h1][h2][vl];
                        sdp[i][s][vl][h1] += dp[i][s][h1][h2][vl];
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int s = 0; s <= 30; s++)
    {
        for (int h1 = 0; h1 <= 10; h1++)
        {
            for (int h2 = 0; h2 <= 10; h2++)
            {
                //if (dp[1][s][h1][h2][s] != 0)
                  //cout << s << ' ' << h1 << ' ' << h2 << ' ' << dp[1][s][h1][h2][s] << endl;
                ans += dp[1][s][h1][h2][s];
            }
        }
    }
    cout << ans << '\n';
}

signed main()
{
    int tc;
    cin >> tc;
    while (tc--)
        testcase();
    return 0;
}

/**
hoping for a miracle
**/

/*
1
2
?????
10 -1
*/

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 110408 KB Output is correct
2 Correct 377 ms 110680 KB Output is correct
3 Correct 404 ms 110424 KB Output is correct
4 Correct 456 ms 110436 KB Output is correct
5 Correct 455 ms 110240 KB Output is correct
6 Correct 490 ms 110428 KB Output is correct
7 Correct 554 ms 110380 KB Output is correct
8 Correct 497 ms 110424 KB Output is correct
9 Correct 413 ms 110428 KB Output is correct
10 Correct 513 ms 110408 KB Output is correct
11 Correct 859 ms 110428 KB Output is correct
12 Correct 247 ms 110408 KB Output is correct
13 Correct 50 ms 110428 KB Output is correct
14 Correct 235 ms 110428 KB Output is correct
15 Correct 60 ms 110424 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 110424 KB Output is correct
2 Correct 501 ms 110428 KB Output is correct
3 Correct 472 ms 110424 KB Output is correct
4 Correct 527 ms 110172 KB Output is correct
5 Correct 556 ms 110424 KB Output is correct
6 Correct 824 ms 110164 KB Output is correct
7 Correct 850 ms 110404 KB Output is correct
8 Correct 816 ms 110424 KB Output is correct
9 Correct 820 ms 110412 KB Output is correct
10 Correct 905 ms 110168 KB Output is correct
11 Correct 905 ms 110428 KB Output is correct
12 Correct 932 ms 110424 KB Output is correct
13 Correct 931 ms 110428 KB Output is correct
14 Execution timed out 1018 ms 110428 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 110428 KB Output is correct
2 Correct 543 ms 110416 KB Output is correct
3 Correct 481 ms 110396 KB Output is correct
4 Correct 481 ms 110416 KB Output is correct
5 Correct 451 ms 110428 KB Output is correct
6 Correct 808 ms 110172 KB Output is correct
7 Correct 816 ms 110428 KB Output is correct
8 Correct 796 ms 110428 KB Output is correct
9 Correct 852 ms 110428 KB Output is correct
10 Execution timed out 1028 ms 110424 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 110412 KB Output is correct
2 Correct 456 ms 110424 KB Output is correct
3 Correct 524 ms 110428 KB Output is correct
4 Correct 463 ms 110168 KB Output is correct
5 Correct 446 ms 110404 KB Output is correct
6 Correct 514 ms 110428 KB Output is correct
7 Correct 479 ms 110424 KB Output is correct
8 Correct 470 ms 110428 KB Output is correct
9 Correct 487 ms 110428 KB Output is correct
10 Correct 598 ms 110428 KB Output is correct
11 Correct 562 ms 110428 KB Output is correct
12 Correct 559 ms 110384 KB Output is correct
13 Correct 505 ms 110172 KB Output is correct
14 Correct 844 ms 110424 KB Output is correct
15 Correct 822 ms 110168 KB Output is correct
16 Correct 847 ms 110416 KB Output is correct
17 Correct 864 ms 110428 KB Output is correct
18 Correct 791 ms 110424 KB Output is correct
19 Correct 792 ms 110412 KB Output is correct
20 Correct 755 ms 110424 KB Output is correct
21 Correct 755 ms 110428 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 110408 KB Output is correct
2 Correct 377 ms 110680 KB Output is correct
3 Correct 404 ms 110424 KB Output is correct
4 Correct 456 ms 110436 KB Output is correct
5 Correct 455 ms 110240 KB Output is correct
6 Correct 490 ms 110428 KB Output is correct
7 Correct 554 ms 110380 KB Output is correct
8 Correct 497 ms 110424 KB Output is correct
9 Correct 413 ms 110428 KB Output is correct
10 Correct 513 ms 110408 KB Output is correct
11 Correct 859 ms 110428 KB Output is correct
12 Correct 247 ms 110408 KB Output is correct
13 Correct 50 ms 110428 KB Output is correct
14 Correct 235 ms 110428 KB Output is correct
15 Correct 60 ms 110424 KB Output is correct
16 Correct 386 ms 110424 KB Output is correct
17 Correct 501 ms 110428 KB Output is correct
18 Correct 472 ms 110424 KB Output is correct
19 Correct 527 ms 110172 KB Output is correct
20 Correct 556 ms 110424 KB Output is correct
21 Correct 824 ms 110164 KB Output is correct
22 Correct 850 ms 110404 KB Output is correct
23 Correct 816 ms 110424 KB Output is correct
24 Correct 820 ms 110412 KB Output is correct
25 Correct 905 ms 110168 KB Output is correct
26 Correct 905 ms 110428 KB Output is correct
27 Correct 932 ms 110424 KB Output is correct
28 Correct 931 ms 110428 KB Output is correct
29 Execution timed out 1018 ms 110428 KB Time limit exceeded
30 Halted 0 ms 0 KB -