oj.uz

Submission #934728

# Submission time Handle Problem Language Result Execution time Memory
934728 2024-02-27T21:23:42 Z andrei_iorgulescu Bowling (BOI15_bow) C++14
33 / 100
 817 ms 55640 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
 
using namespace std;
 
int dp[11][301][32][11][11];
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()
{
    memset(dp,0,sizeof(dp));
    memset(sdp,0,sizeof(sdp));
    memset(sumdp,0,sizeof(sumdp));
    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 + h3][h1][h2]++;
                        }
                    }
                    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 + h3][h1][h2]++;
                        }
                    }
                }
            }
            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 + h3][h1][h2]++;
                        }
                    }
                    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][vl][h1][h2];
                    sdp[n][s][vl][h1] += dp[n][s][vl][h1][h2];
                    //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 vlp = 0; vlp <= 30; vlp++)
            {
                for (int h1 = 0; h1 <= 10; h1++)
                {
                    for (int h2 = 0; h2 <= 10; h2++)
                    {
                        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][10 + h2 + h2p][h1][h2] += dp[i + 1][s + vlp][vlp][h2][h2p];
                        }
                        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][10 + h1p][h1][h2] += 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 vl = 0; vl <= 30; vl++)
            {
                for (int h1 = 0; h1 <= 10; h1++)
                {
                    for (int h2 = 0; h2 <= 10; h2++)
                    {
                        if (!okv(s,i))
                            dp[i][s][vl][h1][h2] = 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][vl][h1][h2];
                        sdp[i][s][vl][h1] += dp[i][s][vl][h1][h2];
                    }
                }
            }
        }
    }
    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][s][h1][h2];
            }
        }
    }
    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 236 ms 55388 KB Output is correct
2 Correct 259 ms 55384 KB Output is correct
3 Correct 289 ms 55388 KB Output is correct
4 Correct 308 ms 55388 KB Output is correct
5 Correct 321 ms 55388 KB Output is correct
6 Correct 369 ms 55384 KB Output is correct
7 Correct 431 ms 55388 KB Output is correct
8 Correct 356 ms 55388 KB Output is correct
9 Correct 308 ms 55384 KB Output is correct
10 Correct 366 ms 55412 KB Output is correct
11 Correct 699 ms 55388 KB Output is correct
12 Correct 126 ms 55388 KB Output is correct
13 Correct 28 ms 55388 KB Output is correct
14 Correct 126 ms 55388 KB Output is correct
15 Correct 33 ms 55388 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 55388 KB Output is correct
2 Correct 356 ms 55384 KB Output is correct
3 Correct 337 ms 55388 KB Output is correct
4 Correct 386 ms 55388 KB Output is correct
5 Correct 411 ms 55384 KB Output is correct
6 Correct 637 ms 55388 KB Output is correct
7 Correct 662 ms 55388 KB Output is correct
8 Correct 656 ms 55384 KB Output is correct
9 Correct 645 ms 55428 KB Output is correct
10 Correct 735 ms 55388 KB Output is correct
11 Correct 739 ms 55388 KB Output is correct
12 Correct 757 ms 55388 KB Output is correct
13 Correct 749 ms 55412 KB Output is correct
14 Correct 817 ms 55292 KB Output is correct
15 Correct 795 ms 55420 KB Output is correct
16 Correct 804 ms 55640 KB Output is correct
17 Correct 799 ms 55384 KB Output is correct
18 Correct 766 ms 55388 KB Output is correct
19 Correct 759 ms 55384 KB Output is correct
20 Correct 785 ms 55488 KB Output is correct
21 Correct 782 ms 55388 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 171 ms 55384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 410 ms 55388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 55388 KB Output is correct
2 Correct 259 ms 55384 KB Output is correct
3 Correct 289 ms 55388 KB Output is correct
4 Correct 308 ms 55388 KB Output is correct
5 Correct 321 ms 55388 KB Output is correct
6 Correct 369 ms 55384 KB Output is correct
7 Correct 431 ms 55388 KB Output is correct
8 Correct 356 ms 55388 KB Output is correct
9 Correct 308 ms 55384 KB Output is correct
10 Correct 366 ms 55412 KB Output is correct
11 Correct 699 ms 55388 KB Output is correct
12 Correct 126 ms 55388 KB Output is correct
13 Correct 28 ms 55388 KB Output is correct
14 Correct 126 ms 55388 KB Output is correct
15 Correct 33 ms 55388 KB Output is correct
16 Correct 300 ms 55388 KB Output is correct
17 Correct 356 ms 55384 KB Output is correct
18 Correct 337 ms 55388 KB Output is correct
19 Correct 386 ms 55388 KB Output is correct
20 Correct 411 ms 55384 KB Output is correct
21 Correct 637 ms 55388 KB Output is correct
22 Correct 662 ms 55388 KB Output is correct
23 Correct 656 ms 55384 KB Output is correct
24 Correct 645 ms 55428 KB Output is correct
25 Correct 735 ms 55388 KB Output is correct
26 Correct 739 ms 55388 KB Output is correct
27 Correct 757 ms 55388 KB Output is correct
28 Correct 749 ms 55412 KB Output is correct
29 Correct 817 ms 55292 KB Output is correct
30 Correct 795 ms 55420 KB Output is correct
31 Correct 804 ms 55640 KB Output is correct
32 Correct 799 ms 55384 KB Output is correct
33 Correct 766 ms 55388 KB Output is correct
34 Correct 759 ms 55384 KB Output is correct
35 Correct 785 ms 55488 KB Output is correct
36 Correct 782 ms 55388 KB Output is correct
37 Incorrect 171 ms 55384 KB Output isn't correct
38 Halted 0 ms 0 KB -