oj.uz

Submission #934721

# Submission time Handle Problem Language Result Execution time Memory
934721 2024-02-27T21:10:08 Z andrei_iorgulescu Bowling (BOI15_bow) C++14
39 / 100
 1000 ms 110680 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()
{
    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][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 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][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 372 ms 110340 KB Output is correct
2 Correct 387 ms 110428 KB Output is correct
3 Correct 408 ms 110424 KB Output is correct
4 Correct 447 ms 110168 KB Output is correct
5 Correct 437 ms 110252 KB Output is correct
6 Correct 499 ms 110404 KB Output is correct
7 Correct 551 ms 110356 KB Output is correct
8 Correct 495 ms 110428 KB Output is correct
9 Correct 431 ms 110168 KB Output is correct
10 Correct 500 ms 110172 KB Output is correct
11 Correct 862 ms 110172 KB Output is correct
12 Correct 235 ms 110428 KB Output is correct
13 Correct 51 ms 110348 KB Output is correct
14 Correct 236 ms 110428 KB Output is correct
15 Correct 60 ms 110428 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 110428 KB Output is correct
2 Correct 477 ms 110428 KB Output is correct
3 Correct 451 ms 110416 KB Output is correct
4 Correct 516 ms 110404 KB Output is correct
5 Correct 538 ms 110168 KB Output is correct
6 Correct 807 ms 110172 KB Output is correct
7 Correct 831 ms 110168 KB Output is correct
8 Correct 827 ms 110172 KB Output is correct
9 Correct 811 ms 110168 KB Output is correct
10 Correct 906 ms 110172 KB Output is correct
11 Correct 925 ms 110172 KB Output is correct
12 Correct 956 ms 110424 KB Output is correct
13 Correct 907 ms 110168 KB Output is correct
14 Execution timed out 1022 ms 110420 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 110200 KB Output is correct
2 Correct 545 ms 110172 KB Output is correct
3 Correct 484 ms 110428 KB Output is correct
4 Correct 476 ms 110168 KB Output is correct
5 Correct 449 ms 110424 KB Output is correct
6 Correct 802 ms 110420 KB Output is correct
7 Correct 814 ms 110400 KB Output is correct
8 Correct 801 ms 110424 KB Output is correct
9 Correct 841 ms 110400 KB Output is correct
10 Correct 986 ms 110172 KB Output is correct
11 Correct 986 ms 110428 KB Output is correct
12 Correct 982 ms 110428 KB Output is correct
13 Execution timed out 1000 ms 110424 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 110168 KB Output is correct
2 Correct 471 ms 110168 KB Output is correct
3 Correct 536 ms 110680 KB Output is correct
4 Correct 443 ms 110172 KB Output is correct
5 Correct 479 ms 110428 KB Output is correct
6 Correct 508 ms 110428 KB Output is correct
7 Correct 473 ms 110168 KB Output is correct
8 Correct 478 ms 110168 KB Output is correct
9 Correct 512 ms 110428 KB Output is correct
10 Correct 592 ms 110408 KB Output is correct
11 Correct 586 ms 110424 KB Output is correct
12 Correct 570 ms 110172 KB Output is correct
13 Correct 531 ms 110168 KB Output is correct
14 Correct 848 ms 110404 KB Output is correct
15 Correct 843 ms 110172 KB Output is correct
16 Correct 867 ms 110404 KB Output is correct
17 Correct 866 ms 110172 KB Output is correct
18 Correct 793 ms 110400 KB Output is correct
19 Correct 813 ms 110428 KB Output is correct
20 Correct 778 ms 110168 KB Output is correct
21 Correct 784 ms 110172 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 110340 KB Output is correct
2 Correct 387 ms 110428 KB Output is correct
3 Correct 408 ms 110424 KB Output is correct
4 Correct 447 ms 110168 KB Output is correct
5 Correct 437 ms 110252 KB Output is correct
6 Correct 499 ms 110404 KB Output is correct
7 Correct 551 ms 110356 KB Output is correct
8 Correct 495 ms 110428 KB Output is correct
9 Correct 431 ms 110168 KB Output is correct
10 Correct 500 ms 110172 KB Output is correct
11 Correct 862 ms 110172 KB Output is correct
12 Correct 235 ms 110428 KB Output is correct
13 Correct 51 ms 110348 KB Output is correct
14 Correct 236 ms 110428 KB Output is correct
15 Correct 60 ms 110428 KB Output is correct
16 Correct 386 ms 110428 KB Output is correct
17 Correct 477 ms 110428 KB Output is correct
18 Correct 451 ms 110416 KB Output is correct
19 Correct 516 ms 110404 KB Output is correct
20 Correct 538 ms 110168 KB Output is correct
21 Correct 807 ms 110172 KB Output is correct
22 Correct 831 ms 110168 KB Output is correct
23 Correct 827 ms 110172 KB Output is correct
24 Correct 811 ms 110168 KB Output is correct
25 Correct 906 ms 110172 KB Output is correct
26 Correct 925 ms 110172 KB Output is correct
27 Correct 956 ms 110424 KB Output is correct
28 Correct 907 ms 110168 KB Output is correct
29 Execution timed out 1022 ms 110420 KB Time limit exceeded
30 Halted 0 ms 0 KB -