oj.uz

Submission #702198

# Submission time Handle Problem Language Result Execution time Memory
702198 2023-02-23T09:59:49 Z LittleCube Bowling (BOI15_bow) C++14
16 / 100
 1000 ms 108876 KB 
#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];
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] = 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++)
                for (int sc = 0; sc <= 330; 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];

    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 (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:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i = 0; i < s.size(); i++)
      |                     ~~^~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 108744 KB Output is correct
2 Correct 287 ms 97416 KB Output is correct
3 Correct 324 ms 97504 KB Output is correct
4 Correct 342 ms 108800 KB Output is correct
5 Correct 325 ms 108748 KB Output is correct
6 Correct 361 ms 108788 KB Output is correct
7 Correct 402 ms 108804 KB Output is correct
8 Correct 370 ms 108828 KB Output is correct
9 Correct 321 ms 108752 KB Output is correct
10 Correct 376 ms 108720 KB Output is correct
11 Correct 577 ms 108800 KB Output is correct
12 Correct 119 ms 18420 KB Output is correct
13 Correct 65 ms 18396 KB Output is correct
14 Correct 118 ms 18552 KB Output is correct
15 Correct 63 ms 18472 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 108796 KB Output is correct
2 Correct 538 ms 108776 KB Output is correct
3 Correct 590 ms 108808 KB Output is correct
4 Correct 491 ms 108836 KB Output is correct
5 Correct 557 ms 108876 KB Output is correct
6 Correct 673 ms 108872 KB Output is correct
7 Correct 957 ms 108804 KB Output is correct
8 Correct 753 ms 108800 KB Output is correct
9 Correct 583 ms 108804 KB Output is correct
10 Execution timed out 1087 ms 108748 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 108664 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1061 ms 108740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 108744 KB Output is correct
2 Correct 287 ms 97416 KB Output is correct
3 Correct 324 ms 97504 KB Output is correct
4 Correct 342 ms 108800 KB Output is correct
5 Correct 325 ms 108748 KB Output is correct
6 Correct 361 ms 108788 KB Output is correct
7 Correct 402 ms 108804 KB Output is correct
8 Correct 370 ms 108828 KB Output is correct
9 Correct 321 ms 108752 KB Output is correct
10 Correct 376 ms 108720 KB Output is correct
11 Correct 577 ms 108800 KB Output is correct
12 Correct 119 ms 18420 KB Output is correct
13 Correct 65 ms 18396 KB Output is correct
14 Correct 118 ms 18552 KB Output is correct
15 Correct 63 ms 18472 KB Output is correct
16 Correct 663 ms 108796 KB Output is correct
17 Correct 538 ms 108776 KB Output is correct
18 Correct 590 ms 108808 KB Output is correct
19 Correct 491 ms 108836 KB Output is correct
20 Correct 557 ms 108876 KB Output is correct
21 Correct 673 ms 108872 KB Output is correct
22 Correct 957 ms 108804 KB Output is correct
23 Correct 753 ms 108800 KB Output is correct
24 Correct 583 ms 108804 KB Output is correct
25 Execution timed out 1087 ms 108748 KB Time limit exceeded
26 Halted 0 ms 0 KB -