結果

問題 No.309 シャイな人たち (1)
ユーザー YuMai6YuMai6
提出日時 2015-12-09 21:04:34
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,136 bytes
コンパイル時間 645 ms
コンパイル使用メモリ 89,408 KB
実行使用メモリ 4,536 KB
最終ジャッジ日時 2023-10-13 08:50:22
合計ジャッジ時間 6,154 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 361 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 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 1 ms
4,348 KB
testcase_14 AC 1 ms
4,348 KB
testcase_15 AC 80 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <math.h>
#include <algorithm>
#include <time.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define llong long long
#define pb(a) push_back(a)
#define INF 2147483640
using namespace std;

int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

int main(){
  int r, c;
  cin >> r >> c;
  double P[r][c];
  int S[r][c];
  REP(i, r) REP(j, c){
    cin >> P[i][j];
    P[i][j]/=100;
  }
  REP(i, r) REP(j, c) cin >> S[i][j];
  
  double dp[(1 << c)], dp1[(1 << c)];
  memset(dp, 0, sizeof(dp));
  memset(dp1, 0, sizeof(dp1));
  int dst[(1 << c)], pt[c];
  dp[0]=1;
  queue<int> q;
  double ans=0;
  
  REP(i, r){
    memset(dp1, 0, sizeof(dp1));
    REP(t, (1 << c)){
      double pr=1;
      REP(j, c){
        if(t & (1 << j))
          pr*=P[i][j];
        else
          pr*=(1-P[i][j]);
      }
      
      memset(dst, -1, sizeof(dst));
      REP(s, (1 << c)){
        if(dst[s & t]==-1){
          memset(pt, 0, sizeof(pt));
          double pr=1;
          REP(j, c){
            if(t & (1 << j)) pt[j]+=4-S[i][j];
            if(s & (1 << j)) pt[j]++;
          }
          
          int u=0;
          REP(j, c) if(pt[j]>=4) q.push(j);
          while(!q.empty()){
            int j=q.front(); q.pop();
            u |= (1 << j);
            if(j-1 >= 0){
              pt[j-1]++;
              if(pt[j-1]==4){
                q.push(j-1);
              }
            }
            if(j+1 < c){
              pt[j+1]++;
              if(pt[j+1]==4){
                q.push(j+1);
              }
            }
          }
          dst[s & t]=u; 
        }
        dp1[dst[s & t]]+=dp[s]*pr;
      }
    }
    
    REP(j, (1 << c)){
      double m=dp[j];
      dp[j]=dp1[j];
      dp1[j]=m;
    }
    
    REP(s, 1 << c){
      ans+=(__builtin_popcount(s)*dp[s]);
    }
    
  }
  printf("%.5f\n", ans);
}
0