提出 #41159152

---

ソースコード 拡げる

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;

template<class T> inline bool chmin(T& a, T b){ if (a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b){ if (a < b){a = b; return true;} return false;}

//using mint = modint998244353;
//using mint = modint1000000007;
//using mint = modint;  // mint::set_mod(p); later
//using mint = static_modint<1000000009>;

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

  // Input
  int N, M, K;
  cin >> N >> M >> K;
  vector<tuple<double, int, int>> ab, cd;

  for (int i = 0; i < N; i++){
    int a, b;
    cin >> a >> b;
    double c = double(a) * 100 / double(a+b);
    ab.emplace_back(c, a, b);
  }

  for (int i = 0; i < M; i++){
    int c, d;
    cin >> c >> d;
    double e = double(c) * 100 / double(c+d);
    cd.emplace_back(e, c, d);
  }

  // Solve: ニブタン
  sort(ab.rbegin(), ab.rend());
  sort(cd.rbegin(), cd.rend());

  double ng = 100;
  double ok = 0;
  for (int i = 0; i < 100; i++){
    double mid = (ok + ng) / 2;
    ll m = 0;
    for (auto p : ab){
      auto [d1, a, b] = p;
      for (auto q : cd){
	auto [d2, c, d] = q;
	double dens = double(a + c) * 100 / double (a + b + c + d);
	if (dens >= mid) m++;
	if (m > K) break;
      }
      if (m > K) break;
    }

    if (m >= K) ok = mid;
    else ng = mid;
  }
  
  cout << fixed << setprecision(12) << ok << endl;
  return 0;
}

提出情報

ジャッジ結果