제출 #1285594

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285594		nemkho	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	431 ms	25996 KiB

snake_escaping

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = (1 << 21) + 5;
string s;
int q, h[N], dp_sub[N], dp_super[N], mask0, mask1, mask2, n, cntbit[N];
void inp()
{
    cin >> n >> q;
    cin >> s;
}
void solve()
{
    for (int mask = 0; mask < (1 << n); mask++)
    {
        cntbit[mask] = __builtin_popcount(mask);
        dp_sub[mask] = dp_super[mask] = h[mask] = s[mask] - '0';
    }
 //   cout << h[1] << "\n";
    for (int k = 0; k < n; k++)
    {
        for (int mask = 0; mask < (1 << n); mask++)
        {
            if (mask & (1 << k))
                dp_sub[mask] += dp_sub[mask ^ (1 << k)];
        }
        for (int mask = (1 << n) - 1; mask >= 0; mask--)
        {
            if (!(mask & (1 << k)))
                dp_super[mask] += dp_super[mask ^ (1 << k)];
        }
    }
    while (q--)
    {
        string t;
        int ans = 0;
        mask1 = mask2 = mask0 = 0;
        cin >> t;
        reverse(t.begin(), t.end());
        for (int i = 0; i < t.length(); i++)
        {
            if (t[i] == '?')
                mask2 |= (1 << i);
            else if (t[i] == '0')
                mask0 |= (1 << i);
            else if (t[i] == '1')
                mask1 |= (1 << i);
        }
        //cout << mask2 << "\n";
        if (cntbit[mask2] <= 6)
        {
            for (int sub = mask2; sub > 0; sub = (sub - 1) & mask2)
            {
               // cout << sub << "\n";
                ans += h[sub | mask1];
            }
            ans += h[mask1];
        }
        else if (cntbit[mask0] <= 6)
        {
            for (int sub = mask0; sub > 0; sub = (sub - 1) & mask0)
            {
                if (cntbit[sub] % 2 == 0)
                    ans += dp_super[sub | mask1];
                else
                    ans -= dp_super[sub | mask1];
            }
            ans += dp_super[mask1];
        }
        else
        {
            for (int sub = mask1; sub > 0; sub = (sub - 1) & mask1)
            {
                if (cntbit[sub] % 2 == 0)
                    ans += dp_sub[(sub ^ mask1) | mask2];
                else
                    ans -= dp_sub[(sub ^ mask1) | mask2];
            }
            ans += dp_sub[mask1 | mask2];
        }
        cout << ans << "\n";
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    inp();
    solve();
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25