#include<cstdio> #include<vector> #include<algorithm> using namespace std; const int DP_SIZE = 100030; const int DP_OFFSET = 50010; double prev_dp[DP_SIZE], curr_dp[DP_SIZE]; double sq(double x) { return x * x; } int main() { int questions, min_points; double inp; scanf("%d%d", &questions, &min_points); vector<double> probab; for (int i = 0; i < questions; i++) { scanf("%lf", &inp); probab.push_back(inp); } for (int i = 0 ; i <= DP_OFFSET; i++) { curr_dp[i] = 1; prev_dp[i] = 1; } double best_probab = 0; sort(probab.begin(), probab.end()); int min_score = 0; int max_score = 0; for (int question_idx = probab.size() - 1; question_idx >= 0; question_idx--) { swap(prev_dp, curr_dp); min_score--; max_score++; for (int new_score = min_score; new_score <= max_score; new_score++) { curr_dp[DP_OFFSET + new_score] = prev_dp[DP_OFFSET + new_score - 1] * probab[question_idx] + prev_dp[DP_OFFSET + new_score + 1] * (1 - probab[question_idx]); } if (curr_dp[DP_OFFSET + min_points] > best_probab) { best_probab = curr_dp[DP_OFFSET + min_points]; } } printf("%.10lf\n", best_probab); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | #include<cstdio> #include<vector> #include<algorithm> using namespace std; const int DP_SIZE = 100030; const int DP_OFFSET = 50010; double prev_dp[DP_SIZE], curr_dp[DP_SIZE]; double sq(double x) { return x * x; } int main() { int questions, min_points; double inp; scanf("%d%d", &questions, &min_points); vector<double> probab; for (int i = 0; i < questions; i++) { scanf("%lf", &inp); probab.push_back(inp); } for (int i = 0 ; i <= DP_OFFSET; i++) { curr_dp[i] = 1; prev_dp[i] = 1; } double best_probab = 0; sort(probab.begin(), probab.end()); int min_score = 0; int max_score = 0; for (int question_idx = probab.size() - 1; question_idx >= 0; question_idx--) { swap(prev_dp, curr_dp); min_score--; max_score++; for (int new_score = min_score; new_score <= max_score; new_score++) { curr_dp[DP_OFFSET + new_score] = prev_dp[DP_OFFSET + new_score - 1] * probab[question_idx] + prev_dp[DP_OFFSET + new_score + 1] * (1 - probab[question_idx]); } if (curr_dp[DP_OFFSET + min_points] > best_probab) { best_probab = curr_dp[DP_OFFSET + min_points]; } } printf("%.10lf\n", best_probab); } |