Submission #1316206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316206		JuanJL	Snake Escaping (JOI18_snake_escaping)	C++20	0 / 100	66 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))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef int ll;

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

ll dp1[MAXP][MAXL];
ll dp2[MAXP][MAXL];
unordered_map<ll,ll> cost;

ll L,Q;
string s; 
vector<ll> one;
	vector<ll> zero;
	vector<ll> qsy;
	ll res = 0;
	ll bina;
	ll newbina;
	ll cnt;

ll f1(ll x, ll y){ // mascara padre
	ll &res = dp1[x][y];
	if(res!=-1) return res;
	if(y==L) return res=max((ll)cost[(int)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(){ FIN;
	cin>>L>>Q;
	cin>>s;

	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){
		one.clear();
		zero.clear();
		qsy.clear();
		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);
		}

		res = 0;

		if(SZ(qsy)<=6){
			forn(h,0,1<<SZ(qsy)){
				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)){
				cnt = 0;
				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)){
				cnt = 0;
				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