#include #include #include #include #include #include #include #include #include #include #include using namespace std; #include template ostream& operator << (ostream& os, vector vec){ for(int i=0; i 111 int compress_B(long long val){ val = (val+mask1)&mask2; //only carry(4) val = ((val&mask3)>>2) | (val&(mask3>>3)); val = ((val&mask4)>>4) | (val&(mask4>>6)); val = ((val&mask5)>>8) | (val&(mask5>>12)); val = ((val&mask6)>>16) | (val&(mask6>>24)); return val; } long long cmask; //0b00000000000011011011011011011011011011011011LL; constexpr long long maskA = 0b00011000011000011000011000011000011000011000LL; //0b00000000001111001111001111001111001111001111LL; constexpr long long maskB = 0b11000000001111000000001111000000001111000000LL; //0b00000000000011111111000011111111000011111111LL; constexpr long long maskC = 0b11111111000000000000000011111111000000000000LL; //0b00001111111111111111000000001111111111111111LL; constexpr long long maskD = 0b00001111111111111111000000000000000000000000LL; constexpr long long maskE = 0b00000000000000000000000000001111111111111111LL; //011011011 -> 111111 int compress_A(long long val){ //val = val&mask0; if(val&mask2){ cerr << bitset<33>(val) << endl; assert((val&mask2)==0); } val = ((val&maskA)>>1) | (val&(maskA>>3)); val = ((val&maskB)>>2) | (val&(maskB>>6)); val = ((val&maskC)>>4) | (val&(maskC>>12)); val = ((val&maskD)>>8) | (val&maskE); return val; } long long propagate(long long val){ long long ret_a = 0; { ret_a = val; int used = 0; for(long long i=0; i<11; i++){ if((used>>i)&1) continue; if(((ret_a>>(3LL*i)) & 7LL) >= 3){ used |= 1<=0; i--){ if((used>>i)&1) continue; if(((ret_a>>(3LL*i)) & 7LL) >= 3){ used |= 1<=0; i--){ if(((ret_a>>(3LL*i)) & 7LL) >= 3){ ret_a &= ~(7LL<<(3*i)); ret_a += (3LL<<(3*i)); } } } /* long long ret_b = 0; { ret_b = val; vector v(11); vector used(11,0); for(long long i=0; i<11; i++){ v[i] = min(3LL, (ret_b>>(3LL*i)) & 7LL); } for(long long i=0; i<11; i++){ if(v[i]>=3 && used[i]==0){ used[i] = 1; if(i+1<11) v[i+1]++; if(i-1>=0) v[i-1]++; } } for(long long i=10; i>=0; i--){ if(v[i]>=3 && used[i]==0){ used[i] = 1; if(i+1<11) v[i+1]++; if(i-1>=0) v[i-1]++; } } ret_b = 0; for(long long i=0; i<11; i++){ v[i] = min(3LL,v[i]); ret_b |= v[i]<<(3LL*i); } ret_b &= cmask; } if(ret_a!=ret_b){ cerr << bitset<34>(val) << " : " << bitset<34>(ret_a) << " , " << bitset<34>(ret_b) << endl; cerr << bitset<34>(cmask) << endl; assert(ret_a == ret_b); } */ return ret_a; } void dfs(vector& memo, int pos, int c, long long val){ if(pos == c){ //propagate long long val_ = compress_A(val); val = propagate(val); int next = compress_B(val); memo[val_] = next; return; } for(long long i=0; i<=3; i++){ dfs(memo, pos+1, c, val + (i<<(pos*3LL))); } } int main(){ int r,c; cin >> r >> c; cmask = (1LL<<(3*c))-1; vector> p(r, vector(c)); for(int i=0; i> p[i][j]; } } vector> s(r, vector(c)); for(int i=0; i> s[i][j]; } } vector expand(1<>j)&1LL)<<(3LL*j); } expand[i] = val; } vector memo(1LL<<(c*2), -1); dfs(memo, 0,c, 0); vector popcount(1LL< Prob(1< Prob_(1< dp(1< dp_(1<>j)&1)?p[i][j]:100-p[i][j]) * 0.01; if((w>>j)&1){ if(s[i][j]==4) zero |= 7LL<<(3LL*j); if(s[i][j]==3) one |= 1LL<<(3LL*j); if(s[i][j]==2) two |= 1LL<<(3LL*j); if(s[i][j]==1) three|= 2LL<<(3LL*j); if(s[i][j]==0) four |= 3LL<<(3LL*j); }else{ zero |= 7LL<<(3LL*j); } } for(int v=0; v<(1<>1LL)&mask0; state_ += (expand[v]&two) << 1LL; state_ += ((~expand[v])&two); state_ += three+(expand[v]&(three>>1LL)); if((state_&mask2) != 0){ cerr << i<<" "<