Submission #697623

#	Time	Username	Problem	Language	Result	Execution time	Memory
697623		peijar	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	1419 ms	460 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

using F = long double;

const int MAXN = 501;
const F INF = 1e18;

F dp[2][MAXN];

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbEtats, nbVoulus;
  cin >> nbEtats >> nbVoulus;

  vector<pair<int, int>> etats(nbEtats);
  int cnt = 0;
  for (auto &[b, a] : etats) {
    cin >> a >> b;
    if (b == -1)
      b = INF;
    else
      cnt++;
  }
  sort(etats.begin(), etats.end());

  F sol = INF;

  for (int c = 0; c <= cnt and c <= nbVoulus; ++c) {
    for (int i = 0; i < 2; ++i)
      for (int j = 0; j < MAXN; ++j)
        dp[i][j] = INF;

    dp[0][0] = 0;
    F s = INF;
    for (int nbVus = 0; nbVus <= nbEtats; ++nbVus) {
      int cur = nbVus % 2;
      int nxt = cur ^ 1;
      for (int i = 0; i < MAXN; ++i)
        dp[nxt][i] = INF;
      for (int prisA = 0; prisA <= nbVus and prisA <= nbVoulus - c; ++prisA) {
        int prisB = nbVus - prisA;
        if (prisB > c)
          continue;
        F v = dp[cur][prisA];
        if (prisB == c) {
          vector<int> restants;
          for (int i = nbVus; i < nbEtats; ++i)
            restants.push_back(etats[i].second);
          sort(restants.begin(), restants.end());
          for (int i = 0; i < nbVoulus - nbVus; ++i)
            v += restants[i] / (F)(c + 1);
          s = min(s, v);
        } else if (nbVus < nbEtats) {
          auto [b, a] = etats[nbVus];
          // on prend en A
          dp[nxt][prisA + 1] = min(dp[nxt][prisA + 1], v + a / (F)(c + 1));
          // on prend en b
          dp[nxt][prisA] = min(dp[nxt][prisA], v + b / (F)(prisB + 1));
        }
      }
    }
    dbg(c, s);
    sol = min(sol, s);
  }

  cout << setprecision(9) << fixed << sol << endl;
}

• 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