Submission #8886806
Source Code Expand
// atcoder/abc034/D/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/
#include <bits/stdc++.h>
#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))
using namespace std;
typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;
template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { each (i, v) is >> i; return is; }
template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }
int main(int argc, char *argv[])
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
while (cin >> n >> k) {
vector<pair<double, double>> v(n);
cin >> v;
auto fn = [&] (double x) {
sort(v.begin(), v.end(), [&] (auto i, auto j) {
return i.first * (i.second - x) > j.first * (j.second - x);
});
double y = 0;
for (int i = 0; i < k; ++i) {
y += v[i].first * (v[i].second - x);
}
return 0 <= y;
};
double small = 0.0;
double large = 200.0;
for (int _ = 0; _ < 100; ++_) {
double mid = (small + large) / 2.0;
if (fn(mid)) small = mid;
else large = mid;
}
printf("%.10lf\n", large);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 食塩水 |
User |
Johniel |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
1744 Byte |
Status |
AC |
Exec Time |
4 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
s0.txt, s1.txt |
All |
000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, s0.txt, s1.txt |
Case Name |
Status |
Exec Time |
Memory |
000.txt |
AC |
4 ms |
256 KB |
001.txt |
AC |
1 ms |
256 KB |
002.txt |
AC |
4 ms |
256 KB |
003.txt |
AC |
2 ms |
256 KB |
004.txt |
AC |
4 ms |
256 KB |
005.txt |
AC |
4 ms |
256 KB |
006.txt |
AC |
4 ms |
256 KB |
007.txt |
AC |
3 ms |
256 KB |
008.txt |
AC |
4 ms |
256 KB |
009.txt |
AC |
1 ms |
256 KB |
010.txt |
AC |
4 ms |
256 KB |
011.txt |
AC |
2 ms |
256 KB |
012.txt |
AC |
4 ms |
256 KB |
013.txt |
AC |
2 ms |
256 KB |
014.txt |
AC |
4 ms |
256 KB |
015.txt |
AC |
3 ms |
256 KB |
016.txt |
AC |
4 ms |
256 KB |
017.txt |
AC |
3 ms |
256 KB |
018.txt |
AC |
4 ms |
256 KB |
019.txt |
AC |
3 ms |
256 KB |
s0.txt |
AC |
1 ms |
256 KB |
s1.txt |
AC |
1 ms |
256 KB |