Submission #729327

#	Time	Username	Problem	Language	Result	Execution time	Memory
729327		tch1cherin	Let's Win the Election (JOI22_ho_t3)	C++17	77 / 100	2540 ms	1480 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
const long double INF = 1e18;
 
void solve() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n), b(n);
  bool good = true;
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> b[i];
    good &= b[i] == -1 || b[i] == a[i];
  }
  if (!good && n != k) {
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
      return b[i] < b[j];
    });
    vector<int> new_a(n), new_b(n);
    for (int i = 0; i < n; i++) {
      new_a[i] = a[order[i]];
      new_b[i] = b[order[i]];
    }
    a = new_a, b = new_b;
    long double ans = INF;
    for (int c = 0; c <= k; c++) {
      vector dp(k + 1, vector<long double>(c + 1, INF));
      dp[0][0] = 0;
      for (int i = 0; i < n; i++) {
        vector new_dp(n + 1, vector<long double>(c + 1, INF));
        for (int j = 0; j <= k; j++) {
          for (int l = 0; l <= c; l++) {
            if (j + 1 <= k && l + 1 <= c && b[i] != -1) {
              new_dp[j + 1][l + 1] = min(new_dp[j + 1][l + 1], dp[j][l] + (long double)b[i] / (l + 1));
            }
            if (j + 1 <= k) {
              new_dp[j + 1][l] = min(new_dp[j + 1][l], dp[j][l] + (long double)a[i] / (c + 1));
            }
            new_dp[j][l] = min(new_dp[j][l], dp[j][l]);
          }
        }
        dp = new_dp;
      }
      for (int i = k; i <= n; i++) {
        ans = min(ans, dp[i][c]);
      }
    }
    cout << ans << "\n";
  } else if (good) {
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
      return a[i] < a[j];
    });
    long double ans = 1e18;
    for (int max_c = 0; max_c <= n; max_c++) {
      int c = 1, cnt = 0;
      long double res = 0;
      for (int i : order) {
        if (a[i] == b[i] && c <= max_c) {
          res += (long double)a[i] / c;
          c++;
          cnt++;
        }
      }
      for (int i : order) {
        if (a[i] != b[i] && cnt < k) {
          res += (long double)a[i] / c;
          cnt++;
        }
      }
      if (cnt >= k) {
        ans = min(ans, res);
      }
    }
    cout << ans << "\n";
  } else {
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
      return b[i] < b[j];
    });
    vector<int> new_a(n), new_b(n);
    for (int i = 0; i < n; i++) {
      new_a[i] = a[order[i]];
      new_b[i] = b[order[i]];
    }
    a = new_a, b = new_b;
    long double ans = INF;
    for (int c = 0; c <= k; c++) {
      vector<long double> dp(c + 1, INF);
      dp[0] = 0;
      for (int i = 0; i < n; i++) {
        vector<long double> new_dp(c + 1, INF);
        for (int l = 0; l <= c; l++) {
          if (l + 1 <= c && b[i] != -1) {
            new_dp[l + 1] = min(new_dp[l + 1], dp[l] + (long double)b[i] / (l + 1));
          }
          new_dp[l] = min(new_dp[l], dp[l] + (long double)a[i] / (c + 1));
        }
        dp = new_dp;
      }
      ans = min(ans, dp[c]);
    }
    cout << ans << "\n";
  }
}
 
int main() {
  cout << fixed << setprecision(9);
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}

• 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: 0 / 23