#include #include #include #include #include using namespace std; constexpr double eps = 1e-20; int R = 0; int C = 0; double solve(const int R, const int C, const vector> & P, const vector> & S); vector preprocess(int n_col); vector calc_points(int know, const vector & s); int get_next_status(int prev, const vector & points); double calc_prob(int mask, const vector & p); int bitcount(int mask){ int counts = 0; while (mask){ if (mask & 1) ++counts; mask >>= 1; } return counts; } int main() { cin >> R >> C; vector< vector > S(R, vector(C, 0)); vector< vector > P(R, vector(C, 0.0)); // read data for (auto & row : P){ for (auto & p : row){ cin >> p; p /= 100.0; } } for (auto & row : S){ for (auto & s : row) cin >> s; } // solve cout << fixed << setprecision(12); cout << solve(R, C, P, S) << endl; return 0; } double solve(const int R, const int C, const vector> & P, const vector> & S){ auto next_status = preprocess(C); double ans = 0; int limit = 1 << C; vector old_prob(1 << C, 0.0); vector new_prob(1 << C, 0.0); old_prob[0] = 1.0; for (int r = 0; r != R; ++r){ auto s = S[r]; auto p = P[r]; for (int know = 0; know != limit; ++know){ auto new_p = calc_prob(know, p); if (new_p <= eps) continue; auto points = calc_points(know, s); for (int prev = 0; prev != limit; ++prev){ auto new_status = next_status[get_next_status(prev, points)]; new_prob[new_status] += old_prob[prev] * new_p; } } for (int status = 0; status != 1 << C; ++status){ ans += new_prob[status] * bitcount(status); } swap(old_prob, new_prob); for (auto & np : new_prob) np = 0; } return ans; } vector preprocess(int n_col){ vector next_status(1 << (2 * n_col), 0); next_status[3] = 1; for (int c = 1; c != n_col; ++c){ int tail_limit = 1 << (2 * c - 2); int head_result_on = 1 << c; for (auto head : {1, 2, 3}){ int head_mask = head << (2 * c); int head_result2 = (head >= 2) ? head_result_on : 0; for (auto neck : {0, 1, 2, 3}){ int neck_mask = neck << (2 * c - 2); int neck_tail_limit = neck_mask + tail_limit; int neck_threshold = 1 << (c - 1); for (int neck_tail = neck_mask; neck_tail != neck_tail_limit; ++neck_tail){ int prev = next_status[neck_tail]; if (prev >= neck_threshold){ next_status[head_mask | neck_tail] = head_result2 + prev; } else if (head != 3){ next_status[head_mask | neck_tail] = prev; } else { next_status[head_mask | neck_tail] = head_result_on + next_status[neck_tail + tail_limit]; } } } } } return next_status; } double calc_prob(int mask, const vector & p){ double prob = 1.0; for (auto pi : p){ prob *= (mask & 1) ? pi : (1 - pi); mask >>= 1; } return prob; } vector calc_points(int know, const vector & s){ vector points; for (int i = 0; i != C; ++i){ if (know & (1 << i)){ points.push_back(3 - s[i]); }else{ points.push_back(-1); } } return points; } int get_next_status(int prev, const vector & points){ int ans = 0; for (int i = 0; i != C; ++i){ int p = points[i]; if (p < 0) continue; if (prev & (1 << i) and p < 3) ++p; ans += (p << (2 * i)); } return ans; }