Submission #817012

#	Time	Username	Problem	Language	Result	Execution time	Memory
817012		kwongweng	Snake Escaping (JOI18_snake_escaping)	C++17	5 / 100	2077 ms	15020 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ll, int> li;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second

int main(){
  ios::sync_with_stdio(false);
  int L, Q; cin>>L>>Q;
  string s; cin >> s;
  int dp[1<<L]; FOR(i,0,(1<<L)) dp[i]=s[i]-'0';
  FOR(i,0,L){
    FOR(mask,0,(1<<L)){
      if (mask & (1<<i)) dp[mask] += dp[mask-(1<<i)];
    }
  }
  FOR(i,0,Q){
    string t; cin >> t; reverse(t.begin(), t.end());
    int cnt=0; FOR(j,0,L) cnt += (t[j]=='?');
    if (cnt <= 20){
      int ans = 0;
      vi a; int cur = 0;
      FOR(j,0,L){
        if (t[j]=='?') a.pb(j);
        else cur += (1<<j)*(t[j]-'0');
      }
      FOR(j,0,(1<<cnt)){
        int val=0; FOR(k,0,cnt){
          if (j & (1<<k)) val += (1<<a[k]);
        }
        //cout<<cur+val<<" ";
        ans+=s[cur+val]-'0';
      }
      cout<<ans<<'\n';
    }
  }
  // x & y = 0 => bits of y = subset of bits of (1<<20)-1-x
}

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