oj.uz

Submission #934720

# Submission time Handle Problem Language Result Execution time Memory
934720 2024-02-27T21:07:19 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()
{
    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 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 412 ms 110416 KB Output is correct
2 Correct 432 ms 110424 KB Output is correct
3 Correct 443 ms 110428 KB Output is correct
4 Correct 477 ms 110428 KB Output is correct
5 Correct 483 ms 110160 KB Output is correct
6 Correct 541 ms 110424 KB Output is correct
7 Correct 609 ms 110428 KB Output is correct
8 Correct 539 ms 110424 KB Output is correct
9 Correct 468 ms 110220 KB Output is correct
10 Correct 548 ms 110428 KB Output is correct
11 Correct 933 ms 110672 KB Output is correct
12 Correct 267 ms 110424 KB Output is correct
13 Correct 61 ms 110428 KB Output is correct
14 Correct 288 ms 110424 KB Output is correct
15 Correct 71 ms 110160 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 110168 KB Output is correct
2 Correct 510 ms 110408 KB Output is correct
3 Correct 494 ms 110220 KB Output is correct
4 Correct 564 ms 110172 KB Output is correct
5 Correct 599 ms 110424 KB Output is correct
6 Correct 853 ms 110408 KB Output is correct
7 Correct 873 ms 110416 KB Output is correct
8 Correct 866 ms 110424 KB Output is correct
9 Correct 863 ms 110172 KB Output is correct
10 Correct 944 ms 110428 KB Output is correct
11 Correct 965 ms 110424 KB Output is correct
12 Correct 981 ms 110168 KB Output is correct
13 Correct 930 ms 110428 KB Output is correct
14 Execution timed out 1025 ms 110424 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 110428 KB Output is correct
2 Correct 604 ms 110428 KB Output is correct
3 Correct 530 ms 110172 KB Output is correct
4 Correct 517 ms 110172 KB Output is correct
5 Correct 521 ms 110428 KB Output is correct
6 Correct 853 ms 110428 KB Output is correct
7 Correct 849 ms 110420 KB Output is correct
8 Correct 861 ms 110332 KB Output is correct
9 Correct 873 ms 110260 KB Output is correct
10 Execution timed out 1002 ms 110428 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 110168 KB Output is correct
2 Correct 501 ms 110168 KB Output is correct
3 Correct 569 ms 110164 KB Output is correct
4 Correct 483 ms 110428 KB Output is correct
5 Correct 488 ms 110424 KB Output is correct
6 Correct 550 ms 110436 KB Output is correct
7 Correct 511 ms 110424 KB Output is correct
8 Correct 499 ms 110428 KB Output is correct
9 Correct 526 ms 110428 KB Output is correct
10 Correct 671 ms 110172 KB Output is correct
11 Correct 609 ms 110428 KB Output is correct
12 Correct 646 ms 110428 KB Output is correct
13 Correct 550 ms 110428 KB Output is correct
14 Correct 901 ms 110172 KB Output is correct
15 Correct 912 ms 110428 KB Output is correct
16 Correct 951 ms 110424 KB Output is correct
17 Correct 932 ms 110424 KB Output is correct
18 Correct 852 ms 110252 KB Output is correct
19 Correct 860 ms 110172 KB Output is correct
20 Correct 858 ms 110424 KB Output is correct
21 Correct 849 ms 110680 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 110416 KB Output is correct
2 Correct 432 ms 110424 KB Output is correct
3 Correct 443 ms 110428 KB Output is correct
4 Correct 477 ms 110428 KB Output is correct
5 Correct 483 ms 110160 KB Output is correct
6 Correct 541 ms 110424 KB Output is correct
7 Correct 609 ms 110428 KB Output is correct
8 Correct 539 ms 110424 KB Output is correct
9 Correct 468 ms 110220 KB Output is correct
10 Correct 548 ms 110428 KB Output is correct
11 Correct 933 ms 110672 KB Output is correct
12 Correct 267 ms 110424 KB Output is correct
13 Correct 61 ms 110428 KB Output is correct
14 Correct 288 ms 110424 KB Output is correct
15 Correct 71 ms 110160 KB Output is correct
16 Correct 401 ms 110168 KB Output is correct
17 Correct 510 ms 110408 KB Output is correct
18 Correct 494 ms 110220 KB Output is correct
19 Correct 564 ms 110172 KB Output is correct
20 Correct 599 ms 110424 KB Output is correct
21 Correct 853 ms 110408 KB Output is correct
22 Correct 873 ms 110416 KB Output is correct
23 Correct 866 ms 110424 KB Output is correct
24 Correct 863 ms 110172 KB Output is correct
25 Correct 944 ms 110428 KB Output is correct
26 Correct 965 ms 110424 KB Output is correct
27 Correct 981 ms 110168 KB Output is correct
28 Correct 930 ms 110428 KB Output is correct
29 Execution timed out 1025 ms 110424 KB Time limit exceeded
30 Halted 0 ms 0 KB -