Submission #4626837
Source Code Expand
#include <algorithm> #include <cassert> #include <cctype> #include <chrono> #define _USE_MATH_DEFINES #include <cmath> #include <cstdio> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iostream> #include <map> #include <queue> #include <random> #include <set> #include <sstream> #include <string> #include <tuple> #include <vector> using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() const int INF = 0x3f3f3f3f, MOD = 1000000007; const long long LINF = 0x3f3f3f3f3f3f3f3fLL; /*-----------------------------------------*/ int n, m, c[4], cost[4], idol[4][10], p[4][10]; double dp[1 << 10]; double rec(int comp) { if (dp[comp] != -1) return dp[comp]; if (comp == (1 << n) - 1) return dp[comp] = 0; dp[comp] = INF; REP(i, m) { int lhs = 100; double rhs = cost[i] * 100; REP(j, c[i]) { if (comp >> idol[i][j] & 1) lhs -= p[i][j]; else rhs += p[i][j] * rec(comp | 1 << idol[i][j]); } if (lhs != 0) dp[comp] = min(dp[comp], rhs / lhs); } return dp[comp]; } int main() { // freopen("input.txt", "r", stdin); cin >> n >> m; REP(i, m) { cin >> c[i] >> cost[i]; REP(j, c[i]) { cin >> idol[i][j] >> p[i][j]; --idol[i][j]; } } REP(i, 1 << n) dp[i] = -1; printf("%.10f\n", rec(0)); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - ソーシャルゲーム |
User | emthrm |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1444 Byte |
Status | AC |
Exec Time | 1 ms |
Memory | 256 KB |
Judge Result
Set Name | A | B | C | D | E | all | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 10 / 10 | 10 / 10 | 10 / 10 | 20 / 20 | 20 / 20 | 30 / 30 | ||||||||||||
Status |
|
|
|
|
|
|
Set Name | Test Cases |
---|---|
A | test_01_ABCDEF.txt, test_02_ABCDEF.txt, test_03_ABCDEF.txt, test_12_ABCDEF.txt |
B | test_01_ABCDEF.txt, test_02_ABCDEF.txt, test_03_ABCDEF.txt, test_04_BCDF.txt, test_05_BCDF.txt, test_06_BCDF.txt, test_07_BCDF.txt, test_08_BCDF.txt, test_09_BCDF.txt, test_11_BCDF.txt, test_12_ABCDEF.txt |
C | test_01_ABCDEF.txt, test_02_ABCDEF.txt, test_03_ABCDEF.txt, test_04_BCDF.txt, test_05_BCDF.txt, test_06_BCDF.txt, test_07_BCDF.txt, test_08_BCDF.txt, test_09_BCDF.txt, test_10_CF.txt, test_11_BCDF.txt, test_12_ABCDEF.txt, test_13_CF.txt, test_14_CDF.txt, test_15_CDF.txt, test_16_CF.txt, test_17_CF.txt, test_18_CF.txt, test_25_CDF.txt, test_26_CDF.txt |
D | test_01_ABCDEF.txt, test_02_ABCDEF.txt, test_03_ABCDEF.txt, test_04_BCDF.txt, test_05_BCDF.txt, test_06_BCDF.txt, test_07_BCDF.txt, test_08_BCDF.txt, test_09_BCDF.txt, test_11_BCDF.txt, test_12_ABCDEF.txt, test_14_CDF.txt, test_15_CDF.txt, test_19_DEF.txt, test_20_DF.txt, test_21_DF.txt, test_22_DF.txt, test_23_DEF.txt, test_24_DF.txt, test_25_CDF.txt, test_26_CDF.txt, test_27_DEF.txt, test_28_DF.txt, test_29_DF.txt, test_30_DF.txt, test_31_DEF.txt, test_32_DF.txt, test_33_DF.txt, test_34_DF.txt, test_35_DEF.txt, test_36_DF.txt, test_37_DF.txt, test_38_DF.txt, test_39_DEF.txt, test_40_DF.txt, test_41_DF.txt, test_42_DF.txt, test_44_DF.txt, test_52_DF.txt |
E | test_01_ABCDEF.txt, test_02_ABCDEF.txt, test_03_ABCDEF.txt, test_12_ABCDEF.txt, test_19_DEF.txt, test_23_DEF.txt, test_27_DEF.txt, test_31_DEF.txt, test_35_DEF.txt, test_39_DEF.txt, test_49_EF.txt, test_51_EF.txt |
all | 00_sample_01_F.txt, 00_sample_02_F.txt, 00_sample_03_F.txt, 00_sample_04_F.txt, 00_sample_05_F.txt, test_01_ABCDEF.txt, test_02_ABCDEF.txt, test_03_ABCDEF.txt, test_04_BCDF.txt, test_05_BCDF.txt, test_06_BCDF.txt, test_07_BCDF.txt, test_08_BCDF.txt, test_09_BCDF.txt, test_10_CF.txt, test_11_BCDF.txt, test_12_ABCDEF.txt, test_13_CF.txt, test_14_CDF.txt, test_15_CDF.txt, test_16_CF.txt, test_17_CF.txt, test_18_CF.txt, test_19_DEF.txt, test_20_DF.txt, test_21_DF.txt, test_22_DF.txt, test_23_DEF.txt, test_24_DF.txt, test_25_CDF.txt, test_26_CDF.txt, test_27_DEF.txt, test_28_DF.txt, test_29_DF.txt, test_30_DF.txt, test_31_DEF.txt, test_32_DF.txt, test_33_DF.txt, test_34_DF.txt, test_35_DEF.txt, test_36_DF.txt, test_37_DF.txt, test_38_DF.txt, test_39_DEF.txt, test_40_DF.txt, test_41_DF.txt, test_42_DF.txt, test_43_F.txt, test_44_DF.txt, test_45_F.txt, test_46_F.txt, test_47_F.txt, test_48_F.txt, test_49_EF.txt, test_50_F.txt, test_51_EF.txt, test_52_DF.txt, test_53_F.txt, test_54_F.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_01_F.txt | AC | 1 ms | 256 KB |
00_sample_02_F.txt | AC | 1 ms | 256 KB |
00_sample_03_F.txt | AC | 1 ms | 256 KB |
00_sample_04_F.txt | AC | 1 ms | 256 KB |
00_sample_05_F.txt | AC | 1 ms | 256 KB |
test_01_ABCDEF.txt | AC | 1 ms | 256 KB |
test_02_ABCDEF.txt | AC | 1 ms | 256 KB |
test_03_ABCDEF.txt | AC | 1 ms | 256 KB |
test_04_BCDF.txt | AC | 1 ms | 256 KB |
test_05_BCDF.txt | AC | 1 ms | 256 KB |
test_06_BCDF.txt | AC | 1 ms | 256 KB |
test_07_BCDF.txt | AC | 1 ms | 256 KB |
test_08_BCDF.txt | AC | 1 ms | 256 KB |
test_09_BCDF.txt | AC | 1 ms | 256 KB |
test_10_CF.txt | AC | 1 ms | 256 KB |
test_11_BCDF.txt | AC | 1 ms | 256 KB |
test_12_ABCDEF.txt | AC | 1 ms | 256 KB |
test_13_CF.txt | AC | 1 ms | 256 KB |
test_14_CDF.txt | AC | 1 ms | 256 KB |
test_15_CDF.txt | AC | 1 ms | 256 KB |
test_16_CF.txt | AC | 1 ms | 256 KB |
test_17_CF.txt | AC | 1 ms | 256 KB |
test_18_CF.txt | AC | 1 ms | 256 KB |
test_19_DEF.txt | AC | 1 ms | 256 KB |
test_20_DF.txt | AC | 1 ms | 256 KB |
test_21_DF.txt | AC | 1 ms | 256 KB |
test_22_DF.txt | AC | 1 ms | 256 KB |
test_23_DEF.txt | AC | 1 ms | 256 KB |
test_24_DF.txt | AC | 1 ms | 256 KB |
test_25_CDF.txt | AC | 1 ms | 256 KB |
test_26_CDF.txt | AC | 1 ms | 256 KB |
test_27_DEF.txt | AC | 1 ms | 256 KB |
test_28_DF.txt | AC | 1 ms | 256 KB |
test_29_DF.txt | AC | 1 ms | 256 KB |
test_30_DF.txt | AC | 1 ms | 256 KB |
test_31_DEF.txt | AC | 1 ms | 256 KB |
test_32_DF.txt | AC | 1 ms | 256 KB |
test_33_DF.txt | AC | 1 ms | 256 KB |
test_34_DF.txt | AC | 1 ms | 256 KB |
test_35_DEF.txt | AC | 1 ms | 256 KB |
test_36_DF.txt | AC | 1 ms | 256 KB |
test_37_DF.txt | AC | 1 ms | 256 KB |
test_38_DF.txt | AC | 1 ms | 256 KB |
test_39_DEF.txt | AC | 1 ms | 256 KB |
test_40_DF.txt | AC | 1 ms | 256 KB |
test_41_DF.txt | AC | 1 ms | 256 KB |
test_42_DF.txt | AC | 1 ms | 256 KB |
test_43_F.txt | AC | 1 ms | 256 KB |
test_44_DF.txt | AC | 1 ms | 256 KB |
test_45_F.txt | AC | 1 ms | 256 KB |
test_46_F.txt | AC | 1 ms | 256 KB |
test_47_F.txt | AC | 1 ms | 256 KB |
test_48_F.txt | AC | 1 ms | 256 KB |
test_49_EF.txt | AC | 1 ms | 256 KB |
test_50_F.txt | AC | 1 ms | 256 KB |
test_51_EF.txt | AC | 1 ms | 256 KB |
test_52_DF.txt | AC | 1 ms | 256 KB |
test_53_F.txt | AC | 1 ms | 256 KB |
test_54_F.txt | AC | 1 ms | 256 KB |