Submission #1036883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036883		juicy	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	161 ms	2448 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 505, inf = 1e9;

int n, k;
int a[N], b[N], ord[N];
double dp[N][N];

double solve(int m) {
  for (int i = 0; i <= n; ++i) {
    fill(dp[i], dp[i] + k + 1, inf);
  }
  dp[0][0] = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= min(i, k - m); ++j) {
      if (dp[i][j] != inf) {
        int id = ord[i + 1];
        if (j + 1 <= k - m) {
          dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + (double) a[id] / (m + 1));
        }
        int pick = i - j;
        if (m - pick > 0) {
          if (b[id] != inf) {
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + (double) b[id] / (pick + 1));
          }
        } else {
          dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
        }
      }
    }
  }
  return dp[n][k - m];
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);


  cin >> n >> k;
  int can = n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i] >> b[i];
    if (b[i] == -1) {
      b[i] = inf;
      --can;
    } 
  }
  iota(ord + 1, ord + n + 1, 1);
  sort(ord + 1, ord + n + 1, [&](int i, int j) {
    return b[i] < b[j];
  });
  double res = solve(1);;
  for (int cnt = 0; cnt <= min(can, k); ++cnt) {
    res = min(res, solve(cnt));
  }  
  cout << fixed << setprecision(15) << res;
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 33 / 33
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23