oj.uz

Submission #934401

# Submission time Handle Problem Language Result Execution time Memory
934401 2024-02-27T09:41:57 Z andrei_iorgulescu Bowling (BOI15_bow) C++14
16 / 100
 1000 ms 110664 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")

using namespace std;
using ll = long long;

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

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 < 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];
                    }
                }
            }
        }
    }
    ll 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 420 ms 110424 KB Output is correct
2 Correct 447 ms 110172 KB Output is correct
3 Correct 468 ms 110424 KB Output is correct
4 Correct 498 ms 110424 KB Output is correct
5 Correct 503 ms 110168 KB Output is correct
6 Correct 578 ms 110428 KB Output is correct
7 Correct 636 ms 110172 KB Output is correct
8 Correct 566 ms 110428 KB Output is correct
9 Correct 501 ms 110172 KB Output is correct
10 Correct 575 ms 110424 KB Output is correct
11 Correct 967 ms 110168 KB Output is correct
12 Correct 294 ms 110428 KB Output is correct
13 Correct 63 ms 110168 KB Output is correct
14 Correct 306 ms 110296 KB Output is correct
15 Correct 72 ms 110424 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 110172 KB Output is correct
2 Correct 559 ms 110172 KB Output is correct
3 Correct 536 ms 110424 KB Output is correct
4 Correct 588 ms 110184 KB Output is correct
5 Correct 624 ms 110428 KB Output is correct
6 Correct 899 ms 110168 KB Output is correct
7 Correct 896 ms 110172 KB Output is correct
8 Correct 905 ms 110172 KB Output is correct
9 Correct 901 ms 110168 KB Output is correct
10 Correct 994 ms 110424 KB Output is correct
11 Execution timed out 1014 ms 110168 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 110424 KB Output is correct
2 Correct 594 ms 110428 KB Output is correct
3 Correct 541 ms 110428 KB Output is correct
4 Correct 543 ms 110424 KB Output is correct
5 Correct 510 ms 110428 KB Output is correct
6 Correct 893 ms 110424 KB Output is correct
7 Correct 911 ms 110172 KB Output is correct
8 Correct 946 ms 110408 KB Output is correct
9 Execution timed out 1004 ms 110412 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 632 ms 110400 KB Output is correct
2 Correct 547 ms 110428 KB Output is correct
3 Correct 659 ms 110428 KB Output is correct
4 Correct 583 ms 110404 KB Output is correct
5 Correct 531 ms 110428 KB Output is correct
6 Correct 585 ms 110428 KB Output is correct
7 Correct 558 ms 110424 KB Output is correct
8 Correct 537 ms 110428 KB Output is correct
9 Correct 578 ms 110172 KB Output is correct
10 Correct 711 ms 110664 KB Output is correct
11 Correct 808 ms 110172 KB Output is correct
12 Correct 697 ms 110424 KB Output is correct
13 Correct 621 ms 110428 KB Output is correct
14 Execution timed out 1040 ms 110428 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 110424 KB Output is correct
2 Correct 447 ms 110172 KB Output is correct
3 Correct 468 ms 110424 KB Output is correct
4 Correct 498 ms 110424 KB Output is correct
5 Correct 503 ms 110168 KB Output is correct
6 Correct 578 ms 110428 KB Output is correct
7 Correct 636 ms 110172 KB Output is correct
8 Correct 566 ms 110428 KB Output is correct
9 Correct 501 ms 110172 KB Output is correct
10 Correct 575 ms 110424 KB Output is correct
11 Correct 967 ms 110168 KB Output is correct
12 Correct 294 ms 110428 KB Output is correct
13 Correct 63 ms 110168 KB Output is correct
14 Correct 306 ms 110296 KB Output is correct
15 Correct 72 ms 110424 KB Output is correct
16 Correct 429 ms 110172 KB Output is correct
17 Correct 559 ms 110172 KB Output is correct
18 Correct 536 ms 110424 KB Output is correct
19 Correct 588 ms 110184 KB Output is correct
20 Correct 624 ms 110428 KB Output is correct
21 Correct 899 ms 110168 KB Output is correct
22 Correct 896 ms 110172 KB Output is correct
23 Correct 905 ms 110172 KB Output is correct
24 Correct 901 ms 110168 KB Output is correct
25 Correct 994 ms 110424 KB Output is correct
26 Execution timed out 1014 ms 110168 KB Time limit exceeded
27 Halted 0 ms 0 KB -