oj.uz

Submission #934727

# Submission time Handle Problem Language Result Execution time Memory
934727 2024-02-27T21:20:43 Z andrei_iorgulescu Bowling (BOI15_bow) C++14
39 / 100
 1000 ms 110676 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][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 385 ms 110164 KB Output is correct
2 Correct 398 ms 110168 KB Output is correct
3 Correct 422 ms 110428 KB Output is correct
4 Correct 461 ms 110564 KB Output is correct
5 Correct 453 ms 110428 KB Output is correct
6 Correct 515 ms 110424 KB Output is correct
7 Correct 581 ms 110168 KB Output is correct
8 Correct 513 ms 110428 KB Output is correct
9 Correct 438 ms 110172 KB Output is correct
10 Correct 518 ms 110172 KB Output is correct
11 Correct 892 ms 110168 KB Output is correct
12 Correct 237 ms 110428 KB Output is correct
13 Correct 54 ms 110424 KB Output is correct
14 Correct 239 ms 110428 KB Output is correct
15 Correct 64 ms 110260 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 110168 KB Output is correct
2 Correct 528 ms 110388 KB Output is correct
3 Correct 487 ms 110416 KB Output is correct
4 Correct 545 ms 110168 KB Output is correct
5 Correct 561 ms 110168 KB Output is correct
6 Correct 821 ms 110424 KB Output is correct
7 Correct 855 ms 110416 KB Output is correct
8 Correct 861 ms 110580 KB Output is correct
9 Correct 832 ms 110420 KB Output is correct
10 Correct 928 ms 110408 KB Output is correct
11 Correct 989 ms 110676 KB Output is correct
12 Execution timed out 1044 ms 110172 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 110168 KB Output is correct
2 Correct 609 ms 110296 KB Output is correct
3 Correct 496 ms 110424 KB Output is correct
4 Correct 512 ms 110428 KB Output is correct
5 Correct 481 ms 110424 KB Output is correct
6 Correct 865 ms 110168 KB Output is correct
7 Correct 871 ms 110408 KB Output is correct
8 Correct 854 ms 110172 KB Output is correct
9 Correct 864 ms 110172 KB Output is correct
10 Execution timed out 1062 ms 110172 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 110356 KB Output is correct
2 Correct 483 ms 110404 KB Output is correct
3 Correct 554 ms 110428 KB Output is correct
4 Correct 463 ms 110428 KB Output is correct
5 Correct 460 ms 110428 KB Output is correct
6 Correct 525 ms 110172 KB Output is correct
7 Correct 519 ms 110428 KB Output is correct
8 Correct 487 ms 110168 KB Output is correct
9 Correct 500 ms 110424 KB Output is correct
10 Correct 651 ms 110172 KB Output is correct
11 Correct 573 ms 110428 KB Output is correct
12 Correct 567 ms 110172 KB Output is correct
13 Correct 533 ms 110276 KB Output is correct
14 Correct 892 ms 110168 KB Output is correct
15 Correct 899 ms 110168 KB Output is correct
16 Correct 869 ms 110424 KB Output is correct
17 Correct 903 ms 110424 KB Output is correct
18 Correct 854 ms 110400 KB Output is correct
19 Correct 816 ms 110312 KB Output is correct
20 Correct 825 ms 110404 KB Output is correct
21 Correct 830 ms 110168 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 110164 KB Output is correct
2 Correct 398 ms 110168 KB Output is correct
3 Correct 422 ms 110428 KB Output is correct
4 Correct 461 ms 110564 KB Output is correct
5 Correct 453 ms 110428 KB Output is correct
6 Correct 515 ms 110424 KB Output is correct
7 Correct 581 ms 110168 KB Output is correct
8 Correct 513 ms 110428 KB Output is correct
9 Correct 438 ms 110172 KB Output is correct
10 Correct 518 ms 110172 KB Output is correct
11 Correct 892 ms 110168 KB Output is correct
12 Correct 237 ms 110428 KB Output is correct
13 Correct 54 ms 110424 KB Output is correct
14 Correct 239 ms 110428 KB Output is correct
15 Correct 64 ms 110260 KB Output is correct
16 Correct 434 ms 110168 KB Output is correct
17 Correct 528 ms 110388 KB Output is correct
18 Correct 487 ms 110416 KB Output is correct
19 Correct 545 ms 110168 KB Output is correct
20 Correct 561 ms 110168 KB Output is correct
21 Correct 821 ms 110424 KB Output is correct
22 Correct 855 ms 110416 KB Output is correct
23 Correct 861 ms 110580 KB Output is correct
24 Correct 832 ms 110420 KB Output is correct
25 Correct 928 ms 110408 KB Output is correct
26 Correct 989 ms 110676 KB Output is correct
27 Execution timed out 1044 ms 110172 KB Time limit exceeded
28 Halted 0 ms 0 KB -