oj.uz

Submission #702236

# Submission time Handle Problem Language Result Execution time Memory
702236 2023-02-23T10:59:12 Z LittleCube Bowling (BOI15_bow) C++14
39 / 100
 1000 ms 110648 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

ll dp[11][66][66][331], pre[11][66][331], sum[66][331];
int cost[66][66][66], cost223[66][66][331], cost23[66][331], cost3[331], can[11][331];
const int s2 = 66, s3 = 241;
string mp2[s2], mp3[s3];

int _cost(string s, string t)
{
    int a = -1, b = -1;
    for (auto c : t)
    {
        if (c == 'x')
            (a == -1 ? a : b) = 10;
        else if (c == '/')
            b = 10 - a;
        else if (isdigit(c))
            (a == -1 ? a : b) = c - '0';
        if (b >= 0)
            break;
    }
    a = max(0, a), b = max(0, b);

    if (s[0] == 'x')
        return 10 + a + b;
    else if (s[1] == '/')
        return 10 + a;
    else
        return s[0] + s[1] - 2 * '0';
}

bool match(string s, string t)
{
    for (int i = 0; i < s.size(); i++)
        if (s[i] != t[i] && s[i] != '?')
            return 0;
    return 1;
}

void solve()
{
    string s;
    int n, ans[13] = {};
    cin >> n >> s;
    for (int i = 1; i <= n; i++)
        cin >> ans[i + 2];
    dp[0][0][0][0] = 1;
    for (int i = 1; i <= n - 1; i++)
        for (int j = 0; j < s2; j++)
            for (int k = 0; k < s2; k++)
                for (int sc = 0; sc <= 330; sc++)
                    dp[i][j][k][sc] = pre[i][j][sc] = sum[k][sc] = 0;
    for (int i = 0; i <= n - 2; i++)
    {
        string t = s.substr(2 * i, 2);
        for (int l = 0; l < s2; l++)
            can[i][l] = match(t, mp2[l]);
    }
    for (int i = 0; i <= n - 2; i++)
        for (int j = 0; j < s2; j++)
            for (int k = 0; k < s2; k++)
                if (j == 65 && k == 65)
                {
                    for (int sc = 0; sc <= 330; sc++)
                    {
                        if (i > 0 && can[i - 1][k])
                            dp[i][j][k][sc] += pre[i][j][sc];
                        if (dp[i][j][k][sc] != 0)
                            for (int l = 0; l < s2; l++)
                                if (can[i][l] && (sc + cost[j][k][l] == ans[i + 1] || ans[i + 1] == -1))
                                    dp[i + 1][k][l][sc + cost[j][k][l]] += dp[i][j][k][sc];
                    }
                }
                else
                {
                    for (int sc = 0; sc <= 330; sc++)
                    {
                        if (i > 0 && can[i - 1][k])
                            dp[i][j][k][sc] += pre[i][j][sc];
                        if (dp[i][j][k][sc] != 0)
                            if (sc + cost[j][k][0] == ans[i + 1] || ans[i + 1] == -1)
                                pre[i + 1][k][sc + cost[j][k][0]] += dp[i][j][k][sc];
                    }
                }

    ll res = 0;
    for (int l = 0; l < s3; l++)
        can[n - 1][l] = match(s.substr(2 * n - 2, 3), mp3[l]);
    for (int j = 0; j < s2; j++)
        for (int k = 0; k < s2; k++)
            if (j == 65 && k == 65)
            {
                for (int sc = 0; sc <= 330; sc++)
                {
                    if (can[n - 2][k])
                        dp[n - 1][j][k][sc] += pre[n - 1][j][sc];
                    if (dp[n - 1][j][k][sc] != 0)
                        for (int l = 0; l < s3; l++)
                            if (can[n - 1][l])
                            {
                                int an2 = cost223[j][k][l], an1 = an2 + cost23[k][l], an = an1 + cost3[l];
                                if ((sc + an2 == ans[n] || ans[n] == -1) &&
                                    (sc + an1 == ans[n + 1] || ans[n + 1] == -1) &&
                                    (sc + an == ans[n + 2] || ans[n + 2] == -1))
                                    res += dp[n - 1][j][k][sc];
                            }
                }
            }
            else
            {
                for (int sc = 0; sc <= 330; sc++)
                {
                    if (can[n - 2][k])
                        dp[n - 1][j][k][sc] += pre[n - 1][j][sc];
                    if (dp[n - 1][j][k][sc] != 0)
                    {
                        int an2 = cost223[j][k][0];
                        if (dp[n - 1][j][k][sc] != 0 &&
                            (sc + an2 == ans[n] || ans[n] == -1))
                            sum[k][sc + an2] += dp[n - 1][j][k][sc];
                    }
                }
            }

    for (int k = 0; k < s2; k++)
        for (int sc = 0; sc <= 330; sc++)
            if (sum[k][sc] != 0)
                for (int l = 0; l < s3; l++)
                    if (can[n - 1][l])
                    {
                        int an1 = cost23[k][l], an = an1 + cost3[l];
                        if ((sc + an1 == ans[n + 1] || ans[n + 1] == -1) &&
                            (sc + an == ans[n + 2] || ans[n + 2] == -1))
                            res += sum[k][sc];
                    }
        
    cout << res << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int idx = 0;
    for (int i = 0; i <= 10; i++)
        for (int j = 0; j <= 10 - i; j++)
        {
            string s = (i == 10 ? "x-" : (i + j == 10 ? string(1, '0' + i) + "/" : string(1, '0' + i) + string(1, '0' + j)));
            mp2[idx] = s;
            idx++;
        }
    idx = 0;
    for (int i = 0; i <= 10; i++)
        for (int j = 0; j <= (i == 10 ? 10 : 10 - i); j++)
            for (int k = 0; k <= (i == 10 ? (j == 10 ? 10 : 10 - j) : (i + j == 10 ? 10 : 0)); k++)
            {
                string s = (i == 10 ? "x" : string(1, '0' + i)) +
                           (j == 10 ? "x" : string(1, '0' + j)) +
                           (k == 10 ? "x" : string(1, '0' + k));
                if (i < 10 && i + j == 10)
                    s[1] = '/';
                if (i == 10 && j < 10 && j + k == 10)
                    s[2] = '/';
                if (i + j < 10)
                    s[2] = '-';
                mp3[idx] = s;
                idx++;
            }
    for (int j = 0; j < s2; j++)
        for (int k = 0; k < s2; k++)
            for (int l = 0; l < s2; l++)
            {
                cost[j][k][l] = _cost(mp2[j], mp2[k] + mp2[l]);
            }
    for (int j = 0; j < s2; j++)
        for (int k = 0; k < s2; k++)
            for (int l = 0; l < s3; l++)
                cost223[j][k][l] = _cost(mp2[j], mp2[k] + mp3[l]);
    for (int k = 0; k < s2; k++)
        for (int l = 0; l < s3; l++)
            cost23[k][l] = _cost(mp2[k], mp3[l]);
    for (int l = 0; l < s3; l++)
    {
        int &an = cost3[l];

        if (mp3[l][1] == '/')
        {
            an += 10;
            if (mp3[l][2] != '-')
                an += (mp3[l][2] == 'x' ? 10 : mp3[l][2] - '0');
        }
        else
        {
            an += (mp3[l][0] == 'x' ? 10 : mp3[l][0] - '0');
            if (mp3[l][2] == '/')
                an += 10;
            else
            {
                an += (mp3[l][1] == 'x' ? 10 : mp3[l][1] - '0');
                if (mp3[l][2] != '-')
                    an += (mp3[l][2] == 'x' ? 10 : mp3[l][2] - '0');
            }
        }
    }

    cerr << "start\n";
    int q;
    cin >> q;
    while (q--)
        solve();
}

Compilation message

bow.cpp: In function 'bool match(std::string, std::string)':
bow.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0; i < s.size(); i++)
      |                     ~~^~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 110412 KB Output is correct
2 Correct 413 ms 99056 KB Output is correct
3 Correct 487 ms 99060 KB Output is correct
4 Correct 477 ms 110544 KB Output is correct
5 Correct 484 ms 110516 KB Output is correct
6 Correct 537 ms 110520 KB Output is correct
7 Correct 608 ms 110512 KB Output is correct
8 Correct 543 ms 110512 KB Output is correct
9 Correct 504 ms 110512 KB Output is correct
10 Correct 565 ms 110516 KB Output is correct
11 Correct 891 ms 110520 KB Output is correct
12 Correct 167 ms 18848 KB Output is correct
13 Correct 70 ms 18752 KB Output is correct
14 Correct 178 ms 18784 KB Output is correct
15 Correct 74 ms 18852 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 110408 KB Output is correct
2 Correct 525 ms 110452 KB Output is correct
3 Correct 543 ms 110512 KB Output is correct
4 Correct 562 ms 110516 KB Output is correct
5 Correct 630 ms 110428 KB Output is correct
6 Correct 851 ms 110516 KB Output is correct
7 Correct 857 ms 110576 KB Output is correct
8 Correct 842 ms 110520 KB Output is correct
9 Correct 828 ms 110520 KB Output is correct
10 Correct 942 ms 110540 KB Output is correct
11 Correct 924 ms 110440 KB Output is correct
12 Correct 951 ms 110524 KB Output is correct
13 Correct 915 ms 110520 KB Output is correct
14 Execution timed out 1002 ms 110520 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 110412 KB Output is correct
2 Correct 606 ms 110520 KB Output is correct
3 Correct 525 ms 110516 KB Output is correct
4 Correct 518 ms 110516 KB Output is correct
5 Correct 498 ms 110516 KB Output is correct
6 Correct 873 ms 110512 KB Output is correct
7 Correct 835 ms 110516 KB Output is correct
8 Correct 832 ms 110512 KB Output is correct
9 Correct 851 ms 110516 KB Output is correct
10 Correct 995 ms 110516 KB Output is correct
11 Correct 970 ms 110520 KB Output is correct
12 Execution timed out 1000 ms 110528 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 110512 KB Output is correct
2 Correct 531 ms 110412 KB Output is correct
3 Correct 563 ms 110612 KB Output is correct
4 Correct 529 ms 110448 KB Output is correct
5 Correct 528 ms 99052 KB Output is correct
6 Correct 601 ms 110516 KB Output is correct
7 Correct 559 ms 110516 KB Output is correct
8 Correct 523 ms 110516 KB Output is correct
9 Correct 563 ms 110520 KB Output is correct
10 Correct 777 ms 110524 KB Output is correct
11 Correct 746 ms 110520 KB Output is correct
12 Correct 654 ms 110520 KB Output is correct
13 Correct 623 ms 110528 KB Output is correct
14 Correct 838 ms 110520 KB Output is correct
15 Correct 866 ms 110528 KB Output is correct
16 Correct 848 ms 110580 KB Output is correct
17 Correct 865 ms 110540 KB Output is correct
18 Correct 817 ms 110524 KB Output is correct
19 Correct 882 ms 110520 KB Output is correct
20 Correct 791 ms 110648 KB Output is correct
21 Correct 809 ms 110528 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 110412 KB Output is correct
2 Correct 413 ms 99056 KB Output is correct
3 Correct 487 ms 99060 KB Output is correct
4 Correct 477 ms 110544 KB Output is correct
5 Correct 484 ms 110516 KB Output is correct
6 Correct 537 ms 110520 KB Output is correct
7 Correct 608 ms 110512 KB Output is correct
8 Correct 543 ms 110512 KB Output is correct
9 Correct 504 ms 110512 KB Output is correct
10 Correct 565 ms 110516 KB Output is correct
11 Correct 891 ms 110520 KB Output is correct
12 Correct 167 ms 18848 KB Output is correct
13 Correct 70 ms 18752 KB Output is correct
14 Correct 178 ms 18784 KB Output is correct
15 Correct 74 ms 18852 KB Output is correct
16 Correct 415 ms 110408 KB Output is correct
17 Correct 525 ms 110452 KB Output is correct
18 Correct 543 ms 110512 KB Output is correct
19 Correct 562 ms 110516 KB Output is correct
20 Correct 630 ms 110428 KB Output is correct
21 Correct 851 ms 110516 KB Output is correct
22 Correct 857 ms 110576 KB Output is correct
23 Correct 842 ms 110520 KB Output is correct
24 Correct 828 ms 110520 KB Output is correct
25 Correct 942 ms 110540 KB Output is correct
26 Correct 924 ms 110440 KB Output is correct
27 Correct 951 ms 110524 KB Output is correct
28 Correct 915 ms 110520 KB Output is correct
29 Execution timed out 1002 ms 110520 KB Time limit exceeded
30 Halted 0 ms 0 KB -