fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. double solve(int n, int k, vector<pair<int, int>> &a, int totalB) {
  5.     vector<vector<double>> dp(n + 1, vector<double>(n + 1, 1e9));
  6.     dp[0][0] = 0;
  7.     for (int i = 1; i <= n; i++) {
  8.         for (int As = 0; As <= min(i - 1, k - totalB); As++) {
  9.             int Bs = min(totalB, i - 1 - As);
  10.             if (As < k - totalB) {
  11.                 double d = a[i].first;
  12.                 dp[i][As + 1] = min(dp[i][As + 1], dp[i - 1][As] + d / (totalB + 1));
  13.             }
  14.             if (Bs < totalB) {
  15.                 double d = a[i].second;
  16.                 dp[i][As] = min(dp[i][As], dp[i - 1][As] + d / (Bs + 1));
  17.             }
  18.             else {
  19.                 dp[i][As] = min(dp[i][As], dp[i - 1][As]);
  20.             }
  21.         }
  22.     }
  23.     return dp[n][k - totalB];
  24. }
  25.  
  26. int main() {
  27.     ios::sync_with_stdio(false);
  28.     int n, k;
  29.     cin >> n >> k;
  30.     vector<pair<int, int>> a(n + 1, {0, 0});
  31.     for (int i = 1; i <= n; i++) {
  32.         cin >> a[i].second >> a[i].first;
  33.         if (a[i].first == -1) a[i].first = 1e9;
  34.     }
  35.     sort(a.begin(), a.end());
  36.     for (int i = 1; i <= n; i++) {
  37.         swap(a[i].first, a[i].second);
  38.     }
  39.     double ans = 1e9;
  40.     int bot = 0, top = k;
  41.     while (bot + 2 < top) {
  42.         int m1 = (bot * 2 + top) / 3;
  43.         int m2 = (bot + top * 2) / 3;
  44.         double ans1 = solve(n, k, a, m1);
  45.         double ans2 = solve(n, k, a, m2);
  46.         ans = min(ans, min(ans1, ans2));
  47.         if (ans1 > ans2) bot = m1;
  48.         else top = m2;
  49.     }
  50.     cout << setprecision(10) << ans << endl;
  51.     return 0;
  52. }
Success #stdin #stdout 0.01s 5380KB
comments (?)
stdin
copy 
20
14
106 277
175 217
170 227
164 245
118 254
139 261
142 270
185 200
162 241
153 239
128 264
103 299
147 248
158 236
160 232
183 205
194 197
135 260
153 234
128 260
stdout
copy 
644.2035714
https://ideone.com/HD8E5t
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!