結果
問題 | No.162 8020運動 |
ユーザー | Hachimori |
提出日時 | 2015-03-06 00:27:32 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 450 ms / 5,000 ms |
コード長 | 1,514 bytes |
コンパイル時間 | 385 ms |
コンパイル使用メモリ | 53,584 KB |
実行使用メモリ | 78,916 KB |
最終ジャッジ日時 | 2023-09-06 15:26:07 |
合計ジャッジ時間 | 9,627 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 26 ms
78,888 KB |
testcase_01 | AC | 208 ms
78,876 KB |
testcase_02 | AC | 334 ms
78,712 KB |
testcase_03 | AC | 449 ms
78,724 KB |
testcase_04 | AC | 443 ms
78,784 KB |
testcase_05 | AC | 442 ms
78,904 KB |
testcase_06 | AC | 450 ms
78,748 KB |
testcase_07 | AC | 446 ms
78,748 KB |
testcase_08 | AC | 443 ms
78,716 KB |
testcase_09 | AC | 25 ms
78,868 KB |
testcase_10 | AC | 334 ms
78,716 KB |
testcase_11 | AC | 211 ms
78,700 KB |
testcase_12 | AC | 90 ms
78,712 KB |
testcase_13 | AC | 447 ms
78,720 KB |
testcase_14 | AC | 33 ms
78,696 KB |
testcase_15 | AC | 33 ms
78,700 KB |
testcase_16 | AC | 99 ms
78,800 KB |
testcase_17 | AC | 43 ms
78,700 KB |
testcase_18 | AC | 425 ms
78,780 KB |
testcase_19 | AC | 300 ms
78,720 KB |
testcase_20 | AC | 358 ms
78,824 KB |
testcase_21 | AC | 352 ms
78,836 KB |
testcase_22 | AC | 335 ms
78,916 KB |
testcase_23 | AC | 352 ms
78,708 KB |
testcase_24 | AC | 330 ms
78,692 KB |
testcase_25 | AC | 373 ms
78,808 KB |
testcase_26 | AC | 25 ms
78,728 KB |
testcase_27 | AC | 231 ms
78,712 KB |
testcase_28 | AC | 416 ms
78,720 KB |
ソースコード
#include<iostream> #include<cstdio> using namespace std; const int YEAR = 21; const int TEETH = 14; const int MASK = 1 << TEETH; int limit; double p[3]; void read() { int age; cin >> age; limit = 80 - age; int pint0, pint1, pint2; cin >> pint0 >> pint1 >> pint2; p[2] = pint0 * 0.01; p[1] = pint1 * 0.01; p[0] = pint2 * 0.01; } double rec(int year, int nth, bool preExist, int mask, double dp[YEAR][TEETH][2][MASK]) { double &ret = dp[year][nth][preExist][mask]; if (ret > -0.5) return ret; if (year == limit) { return ret = __builtin_popcount(mask); } if (nth == TEETH) return ret = rec(year + 1, 0, 0, mask, dp); if (!(mask & (1 << nth))) return ret = rec(year, nth + 1, 0, mask, dp); int nMissing = 0; nMissing += (nth == 0 || !preExist); nMissing += (nth == TEETH - 1 || !(mask & (1 << (nth + 1)))); ret = 0; ret += p[nMissing] * rec(year, nth + 1, 1, mask & ~(1 << nth), dp); ret += (1 - p[nMissing]) * rec(year, nth + 1, 1, mask , dp); return ret; } void work() { static double dp[YEAR][TEETH][2][MASK]; for (int i = 0; i < YEAR; ++i) for (int j = 0; j < TEETH; ++j) for (int k = 0; k < 2; ++k) for (int l = 0; l < MASK; ++l) dp[i][j][k][l] = -1; printf("%.10lf\n", rec(0, 0, 0, (1 << TEETH) - 1, dp) * 2); } int main() { read(); work(); return 0; }