Submission #1158626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158626		Nurlykhan	Snake Escaping (JOI18_snake_escaping)	C++20	5 / 100	2096 ms	5920 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

const int N = (1 << 20) + 10;

int l, q;
int a[N];

int main() {
    #ifdef local
        freopen("input.txt", "r", stdin);
    #endif // local
    string s;
    cin >> l >> q >> s;
    for (int i = 0; i < s.size(); i++) {
        a[i] = s[i] - '0';
    }
    while (q--) {
        string t;
        cin >> t;

        vector<int> not_set;
        int orig_mask = 0;
        for (int i = 0; i < l; i++) {
            if (t[i] == '?') {
                not_set.push_back(i);
            } else if (t[i] == '1') {
                orig_mask |= (1 << (l - i - 1));
            }
        }
        int len = not_set.size();
        int ans = 0;
        for (int mask = 0; mask < (1 << len); mask++) {
            int cur_mask = orig_mask;
            for (int i = 0; i < len; i++) {
                if ((mask >> i) % 2) {
                    cur_mask |= (1 << (l - not_set[i] - 1));
                }
            }
            ans += a[cur_mask];
        }
        cout << ans << endl;
    }
    return 0;
}

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