結果
問題 | No.309 シャイな人たち (1) |
ユーザー |
![]() |
提出日時 | 2015-12-04 23:03:37 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,404 bytes |
コンパイル時間 | 208 ms |
コンパイル使用メモリ | 29,736 KB |
実行使用メモリ | 7,156 KB |
最終ジャッジ日時 | 2023-10-12 14:35:31 |
合計ジャッジ時間 | 23,868 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | AC | 3,219 ms
4,348 KB |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | TLE | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
ソースコード
#include <cstdio> using namespace std; #define Real double #define EPS (Real)(1e-12) #define MAX_H 11 #define MAX_W 11 int h,w; Real p[MAX_H][MAX_W]; int s[MAX_H][MAX_W]; Real result; Real raised[MAX_H+1][1<<MAX_W]; bool know[MAX_W]; int raising; bool raisings[MAX_W]; int active[MAX_W]; int main(){ // INPUT scanf("%d%d",&h,&w); int mask_max = 1<<w; for(int i=0;i<h;++i)for(int j=0;j<w;++j){ int tmp; scanf("%d",&tmp); p[i][j] = (double)tmp/100.0; } for(int i=0;i<h;++i)for(int j=0;j<w;++j){ scanf("%d",&s[i][j]); s[i][j] = 4-s[i][j]; } result = 0.0; raised[0][0] = 1.0; for(int i=0;i<h;++i){ // if know then bit 1, else then bit 0 for(int nowmask=0;nowmask<mask_max;++nowmask){ Real rate = 1.0; for(int j=0;j<w;++j){ if(nowmask>>j & 1 == 1){ rate *= p[i][j]; know[j] = true; }else{ rate *= (1.0-p[i][j]); know[j] = false; } if(rate<EPS)continue; } if(rate<EPS)continue; for(int beforemask=0;beforemask<mask_max;++beforemask){ if(raised[i][beforemask]<EPS)continue; for(int j=0;j<w;++j){ raisings[j] = false; active[j] = s[i][j]+(int)(beforemask>>j&1==1); } for(int j=0;j<w;++j){ if( active[j]>=4 && know[j] ){ raisings[j] = true; } } // from front & left for(int j=1;j<w;++j){ if( !raisings[j] && active[j]>=3 && know[j] && raising>>(j-1)&1==1 ){ raisings[j] = true; } } // from front & right for(int j=w-2;j>=0;--j){ if( !raisings[j] && active[j]>=3 && know[j] && raising>>(j+1)&1==1 ){ raisings[j] = true; } } // from front & left & right for(int j=1;j<w-1;++j){ if( !raisings[j] && active[j]>=2 && know[j] && raising>>(j-1)&1==1 && raising>>(j+1)&1==1 ){ raisings[j] = true; } } raising = 0; for(int j=0;j<w;++j){ if(raisings[j])raising |= (1<<j); } raised[i+1][raising] += rate*raised[i][beforemask]; } } } for(int mask=1;mask<mask_max;++mask){ double cnt = (double)__builtin_popcount(mask); for(int i=0;i<h;++i){ result += raised[i+1][mask]*cnt; } } printf("%.15f\n",result); return 0; }