結果

問題 No.309 シャイな人たち (1)
コンテスト
ユーザー yosupot
提出日時 2015-12-02 00:20:59
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 1,504 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 647 ms
コンパイル使用メモリ 72,868 KB
実行使用メモリ 10,012 KB
最終ジャッジ日時 2024-09-14 07:25:05
合計ジャッジ時間 11,137 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <string>
#include <cassert>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;


const int MN = 11;

int main() {
	int r, c;
	cin >> r >> c;
	static double p[MN][MN];
	static int s[MN][MN];
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> p[i][j];
			p[i][j] /= 100.0;
		}
	}
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> s[i][j];
			s[i][j] = 4-s[i][j];
		}
	}

	static double dp1[1<<MN], dp2[1<<MN];
	double sm = 0;
	dp1[0] = 1.0;
	for (int i = 0; i < r; i++) {
		fill_n(dp2, 1<<MN, 0.0);
		for (int k = 0; k < (1<<c); k++) {
			for (int l = 0; l < (1<<c); l++) {
				double pp = 1;
				static int u[MN];
				for (int m = 0; m < c; m++) {
					pp *= p[i][m];
					u[m] = 0;
					if (l & (1<<m)) u[m] = s[i][m];
					if (k & (1<<m)) u[m]++;
				}
				queue<int> q;
				for (int m = 0; m < c; m++) {
					if (u[m] >= 4) {
						q.push(m);
					}
				}
				int ll = 0;
				while (!q.empty()) {
					int m = q.front(); q.pop();
					if (ll & (1<<m)) continue;
					ll |= (1<<m);
					if (m > 0) {
						u[m-1]++;
						if (u[m-1] == 4) q.push(m-1);
					}
					if (m < c-1) {
						u[m+1]++;
						if (u[m+1] == 4) q.push(m+1);
					}
				}
				dp2[ll] += dp1[k]*pp;
			}
		}
		for (int j = 0; j < (1<<c); j++) {
			dp1[j] = dp2[j];
			sm += dp2[j] * __builtin_popcount(j);
		}

	}
	printf("%.20lf\n", sm);
	return 0;
}
0