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;
using ll = long long;
#define pb push_back
const int MAX_N = 500;
pair<int, int> hours[MAX_N + 5];
double dp[MAX_N + 5][MAX_N + 5];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, k, i, j, v;
double ans;
cin >> n >> k;
for (i = 1; i <= n; i++) {
cin >> hours[i].first >> hours[i].second;
if (hours[i].second == -1) { hours[i].second = INT_MAX; }
}
sort(hours + 1, hours + n + 1, [](pair<int, int> a, pair<int, int> b) {
return (a.second < b.second);
});
ans = INT_MAX;
for (v = 0; v <= k; v++) {
for (i = 0; i <= n; i++) {
for (j = 0; j <= n; j++) {
dp[i][j] = INT_MAX;
}
}
dp[0][0] = 0;
for (i = 1; i <= n; i++) {
for (j = 0; j < i; j++) {
dp[i][j] = min(dp[i][j], dp[i - 1][j] + ((i - j - 1 < v) ? ( (double) hours[i].second / (i - j) ) : 0));
dp[i][j + 1] = min(dp[i][j + 1], dp[i - 1][j] + (double) hours[i].first / (v + 1));
}
}
ans = min(ans, dp[n][k - v]);
}
cout << fixed << setprecision(15) << ans;
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... |