Submission #1316200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316200		JuanJL	Snake Escaping (JOI18_snake_escaping)	C++20	0 / 100	62 ms	131072 KiB

snake_escaping

#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i<b; i++)
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset(a,v,sizeof(a))
using namespace std;
typedef long long ll;

const int MAXL = 21;
const int MAXP = (1<<20)+1;

ll dp1[MAXP][MAXL];
ll dp2[MAXP][MAXL];
ll cost[MAXP];

ll L,Q;

ll f1(ll x, ll y){ // mascara padre
	ll &res = dp1[x][y];
	if(res!=-1) return res;
	if(y==L) return res=max(cost[x],(ll)0);
	res=0; 
	res+=f1(x,y+1);
	res+=f1(x|(1<<y),y+1);
	return res;
}

ll f2(ll x, ll y){ // mascara hijo
	ll &res = dp2[x][y];
	if(res!=-1) return res;
	if(y==L) return res=max(cost[x],(ll)0);
	res=0;
	res+=f2(x,y+1);
	if(x&(1<<y)) res+=f2(x^(1<<y),y+1);
	return res;
}
int main(){
	cin>>L>>Q;
	string s; cin>>s;

	mset(cost,-1);
	mset(dp1,-1);
	mset(dp2,-1);
	
	forn(i,0,1<<L){
		cost[i]=s[i]-'0';
	}

	vector<string> q(Q); forn(i,0,Q) cin>>q[i];

	forn(i,0,Q){
		vector<ll> one;
		vector<ll> zero;
		vector<ll> qsy;
		ll bina = 0;
		forn(j,0,SZ(q[i])){
			if(q[i][j]=='0') zero.pb(j);
			if(q[i][j]=='1') one.pb(j),bina|=(1<<((L-1)-j));
			if(q[i][j]=='?') qsy.pb(j);
		}

		ll res = 0;

		if(SZ(qsy)<=6){
			forn(h,0,1<<SZ(qsy)){
				ll newbina = bina;
				forn(k,0,SZ(qsy)) if(h&(1<<k)){
					newbina|=(1<<((L-1)-qsy[k]));
				}
				if(cost[newbina]!=-1) res+=cost[newbina];
			}
		}else if(SZ(one)<=6){
			forn(h,0,SZ(qsy)) bina|=(1<<((L-1)-qsy[h]));
			res=f2(bina,0);
			forn(h,0,1<<SZ(one)){
				ll cnt = 0;
				ll newbina = bina;
				forn(k,0,SZ(one)) if(h&(1<<k)){
					newbina^=(1<<((L-1)-one[k]));
					cnt++;
				}
				if(cnt%2==0) res+=f2(newbina,0);
				else res-=f2(newbina,0);
			}
		}else{
			res=f1(bina,0);
			forn(h,0,1<<SZ(zero)){
				ll cnt = 0;
				ll newbina = bina;
				forn(k,0,SZ(zero)) if(h&(1<<k)){
					newbina^=(1<<((L-1)-zero[k]));
					cnt++;
				}
				if(cnt%2==0) res+=f1(newbina,0);
				else res-=f1(newbina,0);
			}
		}
		cout<<res<<'\n';
	}
	
	return 0;
}

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