#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define mp make_pair
#define pb push_back
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
constexpr int INF = (int)2e18;
constexpr int N = (int)4e5 + 111;
constexpr int md = (int)1e9+7;
constexpr int mdPower = (int)1e9+7 - 1;
constexpr double eps = 1e-7;
typedef __int128 _uint;
typedef long long ll;
mt19937_64 rnd(time(nullptr));
void add(int& a,int b){
a += b; if(a >= md) a -= md;
}
void sub(int& a,int b){
a -= b; while(a < 0) a += md;
}
void add(__int128& a,int b){
a += b;
}
void sub(__int128& a,int b){
a -= b;
}
int bpow(int a,int b){
if(b == 0)
return 1;
if(b % 2 == 0){
int t = bpow(a,b>>1);
return 1ll*t*t%md;
}
return 1ll * a*bpow(a,b-1) % md;
}
int inv(int a){
return bpow(a,md-2);
}
//int fac[N],invfac[N];
//
//void init(){
// fac[0] = 1;
// for(int i = 1; i < N; i++){
// fac[i] = (fac[i-1] * i) % md;
// }
// invfac[N-1] = inv(fac[N-1]);
// for(int i = N-2; i >= 0; i--){
// invfac[i] = (invfac[i+1] * (i+1))%md;
// }
// return;
//}
//
//int C(int n,int k){
// if(k > n)
// return 0;
// return fac[n] * invfac[k] % md * invfac[n-k] % md;
//}
//
//int A(int n,int k){
// if(k > n)
// return 0;
// return fac[n] * invfac[n-k] % md;
//
void solve(){
int n;
cin >> n;
int k;
cin >> k;
int a[n],b[n];
vector<pair<int,int>> v;
for(int i = 0; i < n; i++){
cin >> a[i] >> b[i];
v.pb(mp(a[i],b[i]));
}
sort(v.begin(),v.end());
for(int i = 0; i < n; i++){
a[i] = v[i].first;
b[i] = v[i].second;
}
long double ans = INF;
v.clear();
for(int cnt2 = 0; cnt2 <= k; cnt2++){ /// dyplomats from right
int r = cnt2;
vector<int> y;
for(int i = k-r; i < n; i++){
if(b[i] != -1)
y.pb(b[i]);
}
if(y.size() < r)
continue;
sort(y.begin(),y.end());
for(int cnt = cnt2; cnt <= k; cnt++){ /// total number of dyplomats
int l = cnt - cnt2;
v.clear();
int sum = 0;
long double t = 0;
int c[1111] = {};
for(int i = 0; i < k-r+1; i++){
// if(a[i] > a[k-r])
// break;
if(b[i] != -1){
v.pb(mp(b[i],-a[i]));
}
if(i < k-r)
sum += a[i];
}
if(v.size() < l)
continue;
sort(v.begin(),v.end());
vector<int> p;
for(int i = 0; i < l; i++){
p.pb(v[i].first);
sum += v[i].second;
}
for(int i = 0; i < r; i++){
p.pb(y[i]);
}
sort(p.begin(),p.end());
if(p.size() != cnt)
continue;
for(int i = 0; i < p.size(); i++){
t += 1.0 * p[i] / (i+1);
}
ans = min(ans,t + 1.0 * sum / (cnt+1));
cerr << cnt << " " << cnt2 << " " << sum << " " << t << "\n";
cerr << "cur = " << t + 1.0 * sum / (cnt+1) << "\n";
}
}
cout << fixed << setprecision(10) << ans << "\n";
return;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int tests = 1;
// cin >> tests;
for(int test = 1; test <= tests; test++){
// cerr << "test = " << test << "\n";
solve();
}
return 0;
}
/**
**/
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:106:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
106 | if(y.size() < r)
| ~~~~~~~~~^~~
Main.cpp:124:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
124 | if(v.size() < l)
| ~~~~~~~~~^~~
Main.cpp:136:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
136 | if(p.size() != cnt)
| ~~~~~~~~~^~~~~~
Main.cpp:138:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for(int i = 0; i < p.size(); i++){
| ~~^~~~~~~~~~
Main.cpp:114:17: warning: unused variable 'c' [-Wunused-variable]
114 | int c[1111] = {};
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2589 ms |
2972 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
