oj.uz

Submission #923552

# Submission time Handle Problem Language Result Execution time Memory
923552 2024-02-07T12:10:49 Z andrei_iorgulescu Bowling (BOI15_bow) C++14
39 / 100
 1000 ms 119808 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")

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];
int kk[105][105][105];

bool ok(int x,int pos,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 < 105; i++)
        for (int j = 0; j < 105; j++)
            for (int k = 0; k < 105; k++)
                kk[i][j][k] = -1;
    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,-1) and ok(h2,2 * n,-1) and ok(h3,2 * n + 1,-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,-1) and ok(h2,2 * n,-1) and ok(h3,2 * n + 1,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,-1) and ok(h2, 2 * n,h1))
                    {
                        for (int h3 = 0; h3 <= 10; h3++)
                        {
                            if (ok(h3,2 * n + 1,-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,-1) and ok(h2,2 * n,h1) and ok(-1,2 * n + 1,-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,-1) and ok(-1,2 * i,-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,-1) and ok(h2,2 * i,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,-1) and ok(h2,2 * i,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 462 ms 119380 KB Output is correct
2 Correct 429 ms 119388 KB Output is correct
3 Correct 459 ms 119388 KB Output is correct
4 Correct 479 ms 119388 KB Output is correct
5 Correct 481 ms 119388 KB Output is correct
6 Correct 550 ms 119468 KB Output is correct
7 Correct 606 ms 119388 KB Output is correct
8 Correct 558 ms 119464 KB Output is correct
9 Correct 474 ms 119384 KB Output is correct
10 Correct 552 ms 119384 KB Output is correct
11 Correct 898 ms 119644 KB Output is correct
12 Correct 282 ms 119384 KB Output is correct
13 Correct 62 ms 119652 KB Output is correct
14 Correct 280 ms 119496 KB Output is correct
15 Correct 75 ms 119808 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 119384 KB Output is correct
2 Correct 548 ms 119472 KB Output is correct
3 Correct 513 ms 119388 KB Output is correct
4 Correct 573 ms 119388 KB Output is correct
5 Correct 614 ms 119384 KB Output is correct
6 Correct 883 ms 119384 KB Output is correct
7 Correct 895 ms 119388 KB Output is correct
8 Correct 872 ms 119388 KB Output is correct
9 Correct 895 ms 119388 KB Output is correct
10 Correct 957 ms 119388 KB Output is correct
11 Correct 996 ms 119388 KB Output is correct
12 Execution timed out 1030 ms 119388 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 119388 KB Output is correct
2 Correct 612 ms 119384 KB Output is correct
3 Correct 538 ms 119468 KB Output is correct
4 Correct 519 ms 119388 KB Output is correct
5 Correct 520 ms 119384 KB Output is correct
6 Correct 859 ms 119384 KB Output is correct
7 Correct 879 ms 119384 KB Output is correct
8 Correct 862 ms 119388 KB Output is correct
9 Correct 894 ms 119388 KB Output is correct
10 Execution timed out 1018 ms 119460 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 119384 KB Output is correct
2 Correct 512 ms 119388 KB Output is correct
3 Correct 581 ms 119384 KB Output is correct
4 Correct 516 ms 119464 KB Output is correct
5 Correct 492 ms 119292 KB Output is correct
6 Correct 553 ms 119388 KB Output is correct
7 Correct 524 ms 119388 KB Output is correct
8 Correct 519 ms 119588 KB Output is correct
9 Correct 550 ms 119388 KB Output is correct
10 Correct 664 ms 119388 KB Output is correct
11 Correct 631 ms 119384 KB Output is correct
12 Correct 610 ms 119384 KB Output is correct
13 Correct 559 ms 119384 KB Output is correct
14 Correct 932 ms 119388 KB Output is correct
15 Correct 908 ms 119388 KB Output is correct
16 Correct 893 ms 119464 KB Output is correct
17 Correct 919 ms 119644 KB Output is correct
18 Correct 840 ms 119384 KB Output is correct
19 Correct 851 ms 119376 KB Output is correct
20 Correct 843 ms 119384 KB Output is correct
21 Correct 843 ms 119640 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 119380 KB Output is correct
2 Correct 429 ms 119388 KB Output is correct
3 Correct 459 ms 119388 KB Output is correct
4 Correct 479 ms 119388 KB Output is correct
5 Correct 481 ms 119388 KB Output is correct
6 Correct 550 ms 119468 KB Output is correct
7 Correct 606 ms 119388 KB Output is correct
8 Correct 558 ms 119464 KB Output is correct
9 Correct 474 ms 119384 KB Output is correct
10 Correct 552 ms 119384 KB Output is correct
11 Correct 898 ms 119644 KB Output is correct
12 Correct 282 ms 119384 KB Output is correct
13 Correct 62 ms 119652 KB Output is correct
14 Correct 280 ms 119496 KB Output is correct
15 Correct 75 ms 119808 KB Output is correct
16 Correct 410 ms 119384 KB Output is correct
17 Correct 548 ms 119472 KB Output is correct
18 Correct 513 ms 119388 KB Output is correct
19 Correct 573 ms 119388 KB Output is correct
20 Correct 614 ms 119384 KB Output is correct
21 Correct 883 ms 119384 KB Output is correct
22 Correct 895 ms 119388 KB Output is correct
23 Correct 872 ms 119388 KB Output is correct
24 Correct 895 ms 119388 KB Output is correct
25 Correct 957 ms 119388 KB Output is correct
26 Correct 996 ms 119388 KB Output is correct
27 Execution timed out 1030 ms 119388 KB Time limit exceeded
28 Halted 0 ms 0 KB -