結果

問題 No.309 シャイな人たち (1)
コンテスト
ユーザー Min_25
提出日時 2015-12-02 00:57:18
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 2,204 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 717 ms
コンパイル使用メモリ 60,020 KB
実行使用メモリ 14,208 KB
最終ジャッジ日時 2024-09-14 07:31:44
合計ジャッジ時間 10,891 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:15:19: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   15 |   uint R, C; scanf("%u %u", &R, &C);
      |              ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:19:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   19 |       uint r; scanf("%u", &r);
      |               ~~~~~^~~~~~~~~~
main.cpp:26:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   26 |       scanf("%u", &S[i][j]);
      |       ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <cstdio>
#include <iostream>
#include <vector>

typedef unsigned uint;
using namespace std;

double P[11][11];
uint S[11][11];

double dp[2][2048];
double pdp[2][2048];

int main() {
  uint R, C; scanf("%u %u", &R, &C);

  for (uint i = 0; i < R; ++i) {
    for (uint j = 0; j < C; ++j) {
      uint r; scanf("%u", &r);
      P[i][j] = double(r) / 100;
    }
  }

  for (uint i = 0; i < R; ++i) {
    for (uint j = 0; j < C; ++j) {
      scanf("%u", &S[i][j]);
    }
  }

  uint total = 1 << C;

  double* curr = dp[0], *next = dp[1];
  double* pcurr = pdp[0], *pnext = pdp[1];
  fill(curr, curr + total, .0);
  fill(pcurr, pcurr + total, .0);

  pcurr[0] = 1.0;
  for (uint y = 0; y < R; ++y) {
    fill(next, next + total, 0);
    fill(pnext, pnext + total, 0);
    for (uint s1 = 0; s1 < total; ++s1) {
      if (pcurr[s1] == 0) {
        continue;
      }
      for (uint s2 = 0; s2 < total; ++s2) {
        uint points[11] = {0};
        uint plus[11] = {0};
        double p = 1.0;
        for (uint x = 0; x < C; ++x) {
          if (s2 & (1 << x)) {
            p *= P[y][x];
            points[x] = 4 - S[y][x];
          } else {
            p *= 1 - P[y][x];
            points[x] = 0;
          }
          if (s1 & (1 << x)) {
            points[x] += 1;
          }
        }
        bool updated = true;
        while (updated) {
          updated = false;
          for (int x = 0; x < C; ++x) {
            uint pl = 0;
            if (x - 1 >= 0 && points[x - 1] >= 4) pl += 1;
            if (x + 1 < C  && points[x + 1] >= 4) pl += 1;
            if (pl > plus[x]) {
              points[x] += pl - plus[x];
              plus[x] = pl;
              updated = true;
            }
          }
        }
        uint nstate = 0;
        uint cnt = 0;
        for (uint x = 0; x < C; ++x) {
          if (points[x] >= 4) {
            nstate |= 1 << x;
            cnt += 1;
          }
        }
        next[nstate] += (curr[s1] + cnt * pcurr[s1]) * p;
        pnext[nstate] += pcurr[s1] * p;
      }
    }
    swap(curr, next);
    swap(pcurr, pnext);
  }
  double ans = 0;
  for (uint i = 0; i < total; ++i) {
    ans += curr[i];
  }
  printf("%.12f\n", ans);
  return 0;
}
0