oj.uz

답안 #923554

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
923554 2024-02-07T12:14:51 Z andrei_iorgulescu Bowling (BOI15_bow) C++14
0 / 100
 1000 ms 112948 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 kk[105][105][105];
bool vaz[105][105][105];

bool ok(int x,int pos,int prec)
{
    if (vaz[x + 1][pos][prec + 1])
        return kk[x + 1][pos][prec + 1];
    vaz[x + 1][pos][prec + 1] = true;
    if (a[pos] == '?')
    {
        kk[x + 1][pos][prec + 1] = true;
        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])
    {
        kk[x + 1][pos][prec + 1] = true;
        return true;
    }
    kk[x + 1][pos][prec + 1] = false;
    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 < 105; i++)
        for (int j = 0; j < 105; j++)
            for (int k = 0; k < 105; k++)
                kk[i][j][k] = vaz[i][j][k] = false;
    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,-1) and ok(h2,2 * n,-1) and ok(h3,2 * n + 1,-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,-1) and ok(h2,2 * n,-1) and ok(h3,2 * n + 1,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,-1) and ok(h2, 2 * n,h1))
                    {
                        for (int h3 = 0; h3 <= 10; h3++)
                        {
                            if (ok(h3,2 * n + 1,-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,-1) and ok(h2,2 * n,h1) and ok(-1,2 * n + 1,-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,-1) and ok(-1,2 * i,-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,-1) and ok(h2,2 * i,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,-1) and ok(h2,2 * i,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
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 537 ms 112580 KB Output is correct
2 Correct 576 ms 112572 KB Output is correct
3 Correct 637 ms 112464 KB Output is correct
4 Correct 670 ms 112636 KB Output is correct
5 Correct 699 ms 112472 KB Output is correct
6 Correct 790 ms 112476 KB Output is correct
7 Correct 927 ms 112476 KB Output is correct
8 Correct 817 ms 112476 KB Output is correct
9 Correct 668 ms 112476 KB Output is correct
10 Correct 817 ms 112472 KB Output is correct
11 Execution timed out 1035 ms 112728 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 819 ms 112472 KB Output is correct
2 Correct 889 ms 112672 KB Output is correct
3 Correct 789 ms 112668 KB Output is correct
4 Correct 941 ms 112668 KB Output is correct
5 Correct 990 ms 112668 KB Output is correct
6 Execution timed out 1065 ms 112948 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 429 ms 112476 KB Output is correct
2 Correct 946 ms 112476 KB Output is correct
3 Correct 799 ms 112476 KB Output is correct
4 Correct 821 ms 112476 KB Output is correct
5 Correct 751 ms 112628 KB Output is correct
6 Execution timed out 1068 ms 112476 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 962 ms 112672 KB Output is correct
2 Correct 766 ms 112688 KB Output is correct
3 Correct 951 ms 112472 KB Output is correct
4 Correct 722 ms 112476 KB Output is correct
5 Correct 766 ms 112544 KB Output is correct
6 Correct 886 ms 112668 KB Output is correct
7 Correct 799 ms 112472 KB Output is correct
8 Correct 795 ms 112672 KB Output is correct
9 Correct 840 ms 112476 KB Output is correct
10 Execution timed out 1014 ms 112472 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 537 ms 112580 KB Output is correct
2 Correct 576 ms 112572 KB Output is correct
3 Correct 637 ms 112464 KB Output is correct
4 Correct 670 ms 112636 KB Output is correct
5 Correct 699 ms 112472 KB Output is correct
6 Correct 790 ms 112476 KB Output is correct
7 Correct 927 ms 112476 KB Output is correct
8 Correct 817 ms 112476 KB Output is correct
9 Correct 668 ms 112476 KB Output is correct
10 Correct 817 ms 112472 KB Output is correct
11 Execution timed out 1035 ms 112728 KB Time limit exceeded
12 Halted 0 ms 0 KB -