結果
問題 | No.309 シャイな人たち (1) |
ユーザー | rickytheta |
提出日時 | 2015-12-04 23:19:22 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 3,029 ms / 4,000 ms |
コード長 | 2,314 bytes |
コンパイル時間 | 286 ms |
コンパイル使用メモリ | 29,564 KB |
実行使用メモリ | 4,356 KB |
最終ジャッジ日時 | 2023-10-12 14:37:25 |
合計ジャッジ時間 | 21,605 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,461 ms
4,352 KB |
testcase_01 | AC | 2,569 ms
4,348 KB |
testcase_02 | AC | 102 ms
4,348 KB |
testcase_03 | AC | 1,913 ms
4,348 KB |
testcase_04 | AC | 24 ms
4,356 KB |
testcase_05 | AC | 334 ms
4,348 KB |
testcase_06 | AC | 42 ms
4,348 KB |
testcase_07 | AC | 183 ms
4,352 KB |
testcase_08 | AC | 2,000 ms
4,348 KB |
testcase_09 | AC | 2,500 ms
4,348 KB |
testcase_10 | AC | 3,029 ms
4,348 KB |
testcase_11 | AC | 2,735 ms
4,348 KB |
testcase_12 | AC | 2,068 ms
4,348 KB |
testcase_13 | AC | 1 ms
4,352 KB |
testcase_14 | AC | 1 ms
4,352 KB |
testcase_15 | AC | 2 ms
4,348 KB |
ソースコード
#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)break; } 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; if(!know[j])continue; active[j] = s[i][j]+(int)(beforemask>>j&1==1); if(j>=1 && active[j]>=3 && raisings[j-1]){ raisings[j] = true; }else if(active[j]>=4){ raisings[j] = true; } } // from front & right for(int j=w-2;j>=0;--j){ if(!know[j])continue; if( !raisings[j] && active[j]>=3 && raisings[j+1] ){ raisings[j] = true; } } // from front & left & right for(int j=1;j<w-1;++j){ if(!know[j])continue; if( !raisings[j] && active[j]>=2 && raisings[j-1] && raisings[j+1] ){ raisings[j] = true; } } raising = 0; for(int j=0;j<w;++j){ raising <<= 1; if(raisings[w-1-j])raising += 1; } 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; }