Submission #1156648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156648		cot7302	Let's Win the Election (JOI22_ho_t3)	C++20	100 / 100	327 ms	2428 KiB

Main

#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
using i64 = long long;
using namespace std;

template <class T>
using vec = vector<T>;

template <class T>
istream& operator>>(istream& is, vec<T>& X) {
  for (auto& x : X) {
    is >> x;
  }
  return is;
}

template <class T>
constexpr T infty = 0;

template <>
constexpr int infty<int> = 1'000'000'000;

template <>
constexpr i64 infty<i64> = 1'000'000'000'000'000'000;

using ld = double;

constexpr ld inf = 1e308;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, K; cin >> N >> K;
  vec<pair<int, int>> BA(N);
  for (auto& [b, a] : BA) {
    cin >> a >> b;
    if (b == -1) {
      b = 777771449;
    }
  }
  sort(ALL(BA));
  vec<vec<ld>> dp(K + 1, vec<ld>(K + 1, inf));
  auto calc = [&](int l) -> ld {
    for (int i = 0; i <= l; i++) {
      for (int j = 0; j <= K; j++) {
        dp[i][j] = inf;
      }
    }
    dp[0][0] = 0;
    for (int i = 0; i < N; i++) {
      auto [b, a] = BA[i];
      for (int j = l; j >= 0; j--) {
        if (j == l) {
          for (int k = K; k > 0; k--) {
            dp[j][k] = min(dp[j][k], dp[j][k - 1] + (ld)a / (l + 1));
            if (j > 0 && b != 777771449) {
              dp[j][k] = min(dp[j][k], dp[j - 1][k - 1] + (ld)b / j);
            }
          }
        }
        else if (i < K) {
          dp[j][i + 1] = min(dp[j][i + 1], dp[j][i] + (ld)a / (l + 1));
          if (j > 0 && b != 777771449) {
            dp[j][i + 1] = min(dp[j][i + 1], dp[j - 1][i] + (ld)b / j);
          }
          dp[j][i] = inf;
        }
      }
    }
    return dp[l][K];
  };
  cout << fixed << setprecision(15);
  ld ans{inf};
  for (int i = 0; i <= K; i++) {
    ans = min(ans, calc(i));
  }
  cout << ans << '\n';
}

• 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