This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Election {
int a, b;
};
bool operator<(const Election &a1, const Election &a2) {
if (a1.b < a2.b) return true;
if (a1.b > a2.b) return false;
if (a1.a < a2.a) return true;
return false;
}
int N, K;
Election E[25];
int main() {
// Step #1. Input
cin >> N >> K;
for (int i = 0; i < N; i++) cin >> E[i].a >> E[i].b;
sort(E, E + N);
// Step #2. Brute Force
double Answer = 1e9;
for (int i = 0; i < (1 << N); i++) {
vector<int> vec;
double Current = 0;
int Votes = 0;
for (int j = 0; j < N; j++) {
if ((i & (1 << j)) == 0 && E[j].b != -1) {
Current += 1.0 * E[j].b / (Votes + 1);
Votes += 1;
}
else {
vec.push_back(E[j].a);
}
}
sort(vec.begin(), vec.end());
for (int j = 0; j < K-Votes; j++) {
Current += 1.0 * vec[j] / (Votes + 1);
}
Answer = min(Answer, Current);
}
// Step #3. Output
printf("%.12lf\n", Answer);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |