제출 #125069

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
125069		wasyl	Bowling (BOI15_bow)	C++11	100 / 100	69 ms	3704 KiB

bow

/*{{{*/
#include <bits/stdc++.h>
#ifdef _GLIBCXX_DEBUG
int c_;
#define cout (c_?cerr:cout)
#define dbg(...) {if(!c_)cerr<<"\033[96;1m";++c_;\
__VA_ARGS__;--c_; if(!c_)cerr<<"\033[0m";}
#else
#define dbg(...)
#endif
#define st first
#define nd second
#define all(...) (__VA_ARGS__).begin(), (__VA_ARGS__).end()
#define dump(...) dbg(print(#__VA_ARGS__, __VA_ARGS__))
#define dump_range(...) dbg(cerr<<#__VA_ARGS__<<": ";print_range(__VA_ARGS__))
using namespace std; using ll = long long; 
template< typename t > using V = vector< t >; void print(){cout<<'\n';}
template< typename t, typename... v > void print(const t& a, v&&... b)
{cout << a << ' '; print(b...);}
template< typename t > void print_range(t a, const t& b)
{while (a!=b) cout << (*a++) << ' '; cout << '\n';}
/*}}}*/

constexpr int maxn = 10, maxb = 10, maxsm = 300;

ll dp[maxn + 1][maxsm + 1][maxb + 1][maxb + 1];
ll sm[maxsm + 1];
ll sm2[maxsm + 1][maxb + 1];
pair< V< V< int > >, V< int > > input();

inline bool proper(int a, int b, int c)
{
    if (a == 10 and b + c <= 10) return true;
    if (a + b == 10 and c <= 10) return true;
    if (a == 10 and b == 10 and c <= 10) return true;
    if (a + b < 10 and c == 0) return true;
    return false;
}

inline bool check(int a, int b, V< int >& mv)
{
    if (a == 10) b = -3;
    else if (a + b == 10) b = -2;

    if ((a == mv[0] or mv[0] == -1) and (b == mv[1] or mv[1] == -1))
        return true;
    return false;
}

inline bool check(int a, int b, int c, V< int >& mv)
{
    if (a == 10)
        if (b != 10 and b + c == 10)
        {
            c = -2;
            goto nieeee;
        }

    if (a + b == 10 and a != 10)
    {
        b = -2;
        goto nieeee;
    }

    if (a + b < 10)
    {
        c = -3;
        goto nieeee;
    }

nieeee:

    dump(a, b, c);

    if (not (a == mv[0] or mv[0] == -1))
        return false;

    if (not (b == mv[1] or mv[1] == -1))
        return false;

    if (not (c == mv[2] or mv[2] == -1))
        return false;

    return true;
}

ll solve()
{
    V< int > pts;
    V< V< int > > mvs;

    tie(mvs, pts) = input();

    int n = pts.size() - 1;

/*{{{*/
dbg(
    dump(n);
    for (auto& v : mvs)
    {
        for (auto& q : v)
            cout << q << ' ';
        cout << '\n';
    }

    for (auto p : pts)
        cout << p << ' ';
    cout << '\n';
);
/*}}}*/

    for (int i = 0; i <= maxn; ++i)
        for (int k = 0; k <= maxsm; ++k)
            for (int a = 0; a <= maxb; ++a)
                for (int b = 0; b <= maxb; ++b)
                    dp[i][k][a][b] = 0;
    
    for (int i = 0; i <= maxsm; ++i)
        dp[0][i][0][0] = (i == pts[0] or pts[0] == -1);

    for (int i = 1; i <= n; ++i)
    {
        auto mv = mvs[i];
        int lok = (pts[i] != -1? pts[i] : 0);
        int hik = (pts[i] != -1? pts[i] : maxsm);

        for (int i = 0; i <= maxsm; ++i)    
            sm[i] = 0;
        
        for (int i = 0; i <= maxsm; ++i)
            for (int c = 0; c <= maxb; ++c)
                sm2[i][c] = 0;

        for (int k = 0; k <= maxsm; ++k)
            for (int c = 0; c <= maxb; ++c)
                for (int d = 0; d <= maxb; ++d)
                    sm[k] += dp[i - 1][k][c][d];

        for (int k = 0; k <= maxsm; ++k)
            for (int c = 0; c <= maxb; ++c)
                for (int d = 0; d <= maxb; ++d)
                    sm2[k][c] += dp[i - 1][k][c][d];

        if (mv.size() == 3)
        {
            for (int a = 0; a <= maxb; ++a)
                for (int b = 0; b <= maxb; ++b)
                    for (int c = 0; c <= maxb; ++c)
                    {
                        if (not proper(a, b, c)) 
                            continue;

                        if (not check(a, b, c, mv))
                            continue;

                        for (int k = lok; k <= hik; ++k)
                        {
                            int pkt = a + b + c;
                            if (k + pkt <= maxsm)
                            {
                                if (dp[i - 1][k + pkt][0][0])
                                {
                                    dump(i, k, a, b, dp[i][k][a][b]);
                                    dump(i - 1, k + pkt, 0, 0, dp[i - 1][k + pkt][0][0]);
                                }
                                dp[i][k][a][b] += 
                                dp[i - 1][k + pkt][0][0];
                            }
                        }
                    }

        }

        if (mv.size() == 2)
        {

            for (int a = 0; a <= maxb; ++a)
                for (int b = 0; b <= maxb - a; ++b)
                {
                    if (not check(a, b, mv))
                        continue;

                    if (a == 10)
                    for (int c = 0; c <= maxb; ++c)
                        for (int d = 0; d <= maxb; ++d)
                            for (int k = lok; k <= hik; ++k)
                            {
                                int pkt = a + b;
                                if (a == 10) pkt += d;
                                if (a + b == 10) pkt += c;

                                if (k + pkt <= maxsm)
                                {
                                    if (dp[i - 1][k + pkt][c][d])
                                    {
                                        dump(i - 1, k + pkt, c, d, dp[i - 1][k + pkt][c][d]);
                                        dump(i, k, a, b, dp[i][k][a][b]);
                                    }
                                    if (a == 10)
                                        dp[i][k][a][c] +=
                                        dp[i - 1][k + pkt][c][d];
                                    else
                                        dp[i][k][a][b] +=
                                        dp[i - 1][k + pkt][c][d];
                                }
                            }

                    if (a != 10 and a + b == 10)
                        for (int c = 0; c <= maxb; ++c)
                            for (int k = lok; k <= hik; ++k)
                            {
                                int pkt = a + b;
                                if (a + b == 10) pkt += c;

                                if (k + pkt <= maxsm)
                                    dp[i][k][a][b] += sm2[k + pkt][c];
                            }

                    if (a != 10 and a + b != 10)
                        for (int k = lok; k <= hik; ++k)
                        {
                            int pkt = a + b;

                            if (k + pkt <= maxsm)
                                dp[i][k][a][b] += sm[k + pkt];
                        }
                }
        }
    }

    ll sum = 0;
    for (int a = 0; a <= maxb; ++a)
        for (int b = 0; b <= maxb; ++b)
            sum += dp[n][0][a][b];
    return sum;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; cin >> t;
    while (t--)
    {
        print(solve());
    }
}

pair< V< V< int > >, V< int > > input()
{
    int n; cin >> n;
    string sl; cin >> sl;
    V< int > ilo(n + 1);

    for (int i = 1; i <= n; ++i)
        cin >> ilo[i];

    reverse(all(ilo));

    V< V< int > > mvs;

    for (int i = 0; i < n; ++i)
    {
        string mv = sl.substr(i * 2, i == n - 1? 3 : 2);

        mvs.push_back(V< int >());

        for (char c : mv)
        {
            if ('0' <= c and c <= '9')
                mvs.back().push_back(c - '0');

            if (c == 'x')
                mvs.back().push_back(10);

            if (c == '/')
                mvs.back().push_back(-2);

            if (c == '?')
                mvs.back().push_back(-1);

            if (c == '-')   
                mvs.back().push_back(-3);
        }
    }

    mvs.push_back(V< int >(2, 0));

    reverse(all(mvs));

    return {mvs, ilo};
}

• Subtask 1: 16 / 16
• Subtask 2: 17 / 17
• Subtask 3: 26 / 26
• Subtask 4: 23 / 23
• Subtask 5: 18 / 18