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 <bits/stdc++.h>
using namespace std;
const int MN = 501;
const double INF = 1e18;
struct stat {
double a, b;
bool operator < (const stat &rhs) const {
return make_pair((b < 0) ? INF : b, -a) < make_pair((rhs.b < 0) ? INF : rhs.b, -rhs.a);
}
} A[MN];
int n, k;
double DP[MN][MN][MN];
int main() {
cin >> n >> k;
for(int i = 0; i <= n; ++i)
for(int j = 0; j <= n + 1; ++j)
for(int w = 0; w <= k; ++w)
DP[i][j][w] = INF;
for(int i = 1; i <= n; ++i) {
cin >> A[i].a >> A[i].b;
}
sort(A + 1, A + n + 1);
DP[0][1][0] = 0;
for(int i = 0; i < n; ++i) {
for(int j = 1; j <= n + 1; ++j) {
for(int w = 0; w <= k; ++w) {
///propag (i, j, w) in orasul i + 1
DP[i + 1][j][w] = min(DP[i + 1][j][w], DP[i][j][w]);
DP[i + 1][j][w + 1] = min(DP[i + 1][j][w + 1], DP[i][j][w] + (A[i + 1].a / double(j)));
if(A[i + 1].b >= 0)
DP[i + 1][j + 1][w + 1] = min(DP[i + 1][j + 1][w + 1], DP[i][j][w] + (A[i + 1].b / double(j)));
}
}
}
double re = INF;
for(int j = 1; j <= n + 1; ++j)
re = min(re, DP[n][j][k]);
cout << fixed << setprecision(10) << re << "\n";
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... |