oj.uz

Submission #923539

# Submission time Handle Problem Language Result Execution time Memory
923539 2024-02-07T11:51:00 Z andrei_iorgulescu Bowling (BOI15_bow) C++14
39 / 100
 1000 ms 110768 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];
 
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 393 ms 110424 KB Output is correct
2 Correct 411 ms 110424 KB Output is correct
3 Correct 445 ms 110424 KB Output is correct
4 Correct 470 ms 110172 KB Output is correct
5 Correct 475 ms 110172 KB Output is correct
6 Correct 536 ms 110172 KB Output is correct
7 Correct 603 ms 110428 KB Output is correct
8 Correct 536 ms 110424 KB Output is correct
9 Correct 459 ms 110424 KB Output is correct
10 Correct 538 ms 110168 KB Output is correct
11 Correct 889 ms 110172 KB Output is correct
12 Correct 271 ms 110428 KB Output is correct
13 Correct 58 ms 110172 KB Output is correct
14 Correct 263 ms 110428 KB Output is correct
15 Correct 68 ms 110172 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 110168 KB Output is correct
2 Correct 521 ms 110172 KB Output is correct
3 Correct 496 ms 110172 KB Output is correct
4 Correct 557 ms 110420 KB Output is correct
5 Correct 585 ms 110404 KB Output is correct
6 Correct 861 ms 110424 KB Output is correct
7 Correct 884 ms 110404 KB Output is correct
8 Correct 889 ms 110168 KB Output is correct
9 Correct 854 ms 110172 KB Output is correct
10 Correct 968 ms 110168 KB Output is correct
11 Correct 955 ms 110172 KB Output is correct
12 Correct 985 ms 110172 KB Output is correct
13 Correct 956 ms 110172 KB Output is correct
14 Execution timed out 1055 ms 110172 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 110768 KB Output is correct
2 Correct 576 ms 110168 KB Output is correct
3 Correct 527 ms 110168 KB Output is correct
4 Correct 509 ms 110168 KB Output is correct
5 Correct 479 ms 110428 KB Output is correct
6 Correct 846 ms 110168 KB Output is correct
7 Correct 870 ms 110172 KB Output is correct
8 Correct 830 ms 110428 KB Output is correct
9 Correct 879 ms 110172 KB Output is correct
10 Execution timed out 1026 ms 110168 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 540 ms 110172 KB Output is correct
2 Correct 501 ms 110420 KB Output is correct
3 Correct 578 ms 110424 KB Output is correct
4 Correct 485 ms 110428 KB Output is correct
5 Correct 485 ms 110428 KB Output is correct
6 Correct 548 ms 110616 KB Output is correct
7 Correct 502 ms 110168 KB Output is correct
8 Correct 501 ms 110424 KB Output is correct
9 Correct 529 ms 110428 KB Output is correct
10 Correct 638 ms 110168 KB Output is correct
11 Correct 614 ms 110168 KB Output is correct
12 Correct 593 ms 110416 KB Output is correct
13 Correct 550 ms 110592 KB Output is correct
14 Correct 878 ms 110168 KB Output is correct
15 Correct 893 ms 110168 KB Output is correct
16 Correct 890 ms 110168 KB Output is correct
17 Correct 913 ms 110172 KB Output is correct
18 Correct 819 ms 110172 KB Output is correct
19 Correct 849 ms 110172 KB Output is correct
20 Correct 820 ms 110168 KB Output is correct
21 Correct 817 ms 110424 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 110424 KB Output is correct
2 Correct 411 ms 110424 KB Output is correct
3 Correct 445 ms 110424 KB Output is correct
4 Correct 470 ms 110172 KB Output is correct
5 Correct 475 ms 110172 KB Output is correct
6 Correct 536 ms 110172 KB Output is correct
7 Correct 603 ms 110428 KB Output is correct
8 Correct 536 ms 110424 KB Output is correct
9 Correct 459 ms 110424 KB Output is correct
10 Correct 538 ms 110168 KB Output is correct
11 Correct 889 ms 110172 KB Output is correct
12 Correct 271 ms 110428 KB Output is correct
13 Correct 58 ms 110172 KB Output is correct
14 Correct 263 ms 110428 KB Output is correct
15 Correct 68 ms 110172 KB Output is correct
16 Correct 407 ms 110168 KB Output is correct
17 Correct 521 ms 110172 KB Output is correct
18 Correct 496 ms 110172 KB Output is correct
19 Correct 557 ms 110420 KB Output is correct
20 Correct 585 ms 110404 KB Output is correct
21 Correct 861 ms 110424 KB Output is correct
22 Correct 884 ms 110404 KB Output is correct
23 Correct 889 ms 110168 KB Output is correct
24 Correct 854 ms 110172 KB Output is correct
25 Correct 968 ms 110168 KB Output is correct
26 Correct 955 ms 110172 KB Output is correct
27 Correct 985 ms 110172 KB Output is correct
28 Correct 956 ms 110172 KB Output is correct
29 Execution timed out 1055 ms 110172 KB Time limit exceeded
30 Halted 0 ms 0 KB -