oj.uz

Submission #702230

# Submission time Handle Problem Language Result Execution time Memory
702230 2023-02-23T10:48:14 Z LittleCube Bowling (BOI15_bow) C++14
16 / 100
 1000 ms 110420 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];
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] = 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++)
            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 (dp[n - 1][j][k][sc] != 0 &&
                                (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];
                        }
            }
    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 332 ms 110348 KB Output is correct
2 Correct 363 ms 98876 KB Output is correct
3 Correct 431 ms 98836 KB Output is correct
4 Correct 412 ms 110388 KB Output is correct
5 Correct 440 ms 110344 KB Output is correct
6 Correct 473 ms 110352 KB Output is correct
7 Correct 517 ms 110340 KB Output is correct
8 Correct 487 ms 110340 KB Output is correct
9 Correct 417 ms 110340 KB Output is correct
10 Correct 488 ms 110344 KB Output is correct
11 Correct 836 ms 110340 KB Output is correct
12 Correct 200 ms 18668 KB Output is correct
13 Correct 81 ms 18624 KB Output is correct
14 Correct 209 ms 18612 KB Output is correct
15 Correct 82 ms 18664 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 110340 KB Output is correct
2 Correct 652 ms 110340 KB Output is correct
3 Correct 649 ms 110340 KB Output is correct
4 Correct 575 ms 110412 KB Output is correct
5 Correct 593 ms 110268 KB Output is correct
6 Correct 824 ms 110344 KB Output is correct
7 Correct 904 ms 110340 KB Output is correct
8 Correct 842 ms 110336 KB Output is correct
9 Correct 780 ms 110344 KB Output is correct
10 Execution timed out 1062 ms 110284 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 886 ms 110344 KB Output is correct
2 Correct 576 ms 110400 KB Output is correct
3 Correct 536 ms 110420 KB Output is correct
4 Correct 499 ms 110344 KB Output is correct
5 Correct 444 ms 110284 KB Output is correct
6 Correct 765 ms 110344 KB Output is correct
7 Correct 781 ms 110344 KB Output is correct
8 Correct 765 ms 110340 KB Output is correct
9 Correct 818 ms 110340 KB Output is correct
10 Execution timed out 1000 ms 110412 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 110412 KB Output is correct
2 Correct 493 ms 110408 KB Output is correct
3 Correct 604 ms 110344 KB Output is correct
4 Correct 535 ms 110272 KB Output is correct
5 Correct 477 ms 98888 KB Output is correct
6 Correct 524 ms 110264 KB Output is correct
7 Correct 510 ms 110348 KB Output is correct
8 Correct 488 ms 110376 KB Output is correct
9 Correct 514 ms 110340 KB Output is correct
10 Execution timed out 1018 ms 110280 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 110348 KB Output is correct
2 Correct 363 ms 98876 KB Output is correct
3 Correct 431 ms 98836 KB Output is correct
4 Correct 412 ms 110388 KB Output is correct
5 Correct 440 ms 110344 KB Output is correct
6 Correct 473 ms 110352 KB Output is correct
7 Correct 517 ms 110340 KB Output is correct
8 Correct 487 ms 110340 KB Output is correct
9 Correct 417 ms 110340 KB Output is correct
10 Correct 488 ms 110344 KB Output is correct
11 Correct 836 ms 110340 KB Output is correct
12 Correct 200 ms 18668 KB Output is correct
13 Correct 81 ms 18624 KB Output is correct
14 Correct 209 ms 18612 KB Output is correct
15 Correct 82 ms 18664 KB Output is correct
16 Correct 501 ms 110340 KB Output is correct
17 Correct 652 ms 110340 KB Output is correct
18 Correct 649 ms 110340 KB Output is correct
19 Correct 575 ms 110412 KB Output is correct
20 Correct 593 ms 110268 KB Output is correct
21 Correct 824 ms 110344 KB Output is correct
22 Correct 904 ms 110340 KB Output is correct
23 Correct 842 ms 110336 KB Output is correct
24 Correct 780 ms 110344 KB Output is correct
25 Execution timed out 1062 ms 110284 KB Time limit exceeded
26 Halted 0 ms 0 KB -