oj.uz

Submission #702199

# Submission time Handle Problem Language Result Execution time Memory
702199 2023-02-23T10:01:26 Z LittleCube Bowling (BOI15_bow) C++14
16 / 100
 1000 ms 108828 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];
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: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 239 ms 108736 KB Output is correct
2 Correct 287 ms 97484 KB Output is correct
3 Correct 312 ms 97616 KB Output is correct
4 Correct 317 ms 108776 KB Output is correct
5 Correct 338 ms 108800 KB Output is correct
6 Correct 354 ms 108800 KB Output is correct
7 Correct 397 ms 108796 KB Output is correct
8 Correct 376 ms 108796 KB Output is correct
9 Correct 330 ms 108740 KB Output is correct
10 Correct 366 ms 108796 KB Output is correct
11 Correct 551 ms 108800 KB Output is correct
12 Correct 114 ms 18600 KB Output is correct
13 Correct 59 ms 18380 KB Output is correct
14 Correct 110 ms 18424 KB Output is correct
15 Correct 63 ms 18488 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 659 ms 108796 KB Output is correct
2 Correct 542 ms 108800 KB Output is correct
3 Correct 583 ms 108796 KB Output is correct
4 Correct 457 ms 108800 KB Output is correct
5 Correct 536 ms 108700 KB Output is correct
6 Correct 652 ms 108800 KB Output is correct
7 Correct 912 ms 108796 KB Output is correct
8 Correct 753 ms 108800 KB Output is correct
9 Correct 613 ms 108828 KB Output is correct
10 Execution timed out 1081 ms 108720 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 1078 ms 108756 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 1074 ms 108668 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 108736 KB Output is correct
2 Correct 287 ms 97484 KB Output is correct
3 Correct 312 ms 97616 KB Output is correct
4 Correct 317 ms 108776 KB Output is correct
5 Correct 338 ms 108800 KB Output is correct
6 Correct 354 ms 108800 KB Output is correct
7 Correct 397 ms 108796 KB Output is correct
8 Correct 376 ms 108796 KB Output is correct
9 Correct 330 ms 108740 KB Output is correct
10 Correct 366 ms 108796 KB Output is correct
11 Correct 551 ms 108800 KB Output is correct
12 Correct 114 ms 18600 KB Output is correct
13 Correct 59 ms 18380 KB Output is correct
14 Correct 110 ms 18424 KB Output is correct
15 Correct 63 ms 18488 KB Output is correct
16 Correct 659 ms 108796 KB Output is correct
17 Correct 542 ms 108800 KB Output is correct
18 Correct 583 ms 108796 KB Output is correct
19 Correct 457 ms 108800 KB Output is correct
20 Correct 536 ms 108700 KB Output is correct
21 Correct 652 ms 108800 KB Output is correct
22 Correct 912 ms 108796 KB Output is correct
23 Correct 753 ms 108800 KB Output is correct
24 Correct 613 ms 108828 KB Output is correct
25 Execution timed out 1081 ms 108720 KB Time limit exceeded
26 Halted 0 ms 0 KB -