#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int INF = 1e18;
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
bool cmp(pair<int,int> a, pair<int,int> b){
if(a.second == b.second) return a.first<b.first;
return a.second < b.second;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout<<setprecision(3)<<fixed;
int n,k1; cin>>n>>k1;
vector<pair<int,int>> v(n);
for(int i = 0; i<n; i++){
cin>>v[i].first>>v[i].second;
if(v[i].second == -1) v[i].second = INF;
}
long double ans = INF;
for(int x = 0; x <= k1; x++){
int buy = k1-x;
// cheaper way to buy buy
vector<long double> dp(x+1, INF);
vector<pair<int,int>> act = v;
map<pair<int,int>, int> curinsum, curinb, tot;
sort(act.begin(),act.end());
for(auto y : act) tot[y]++;
dp[0] = 0;
for(int i = 0; i<buy; i++) dp[0] += 1.0 * act[i].first / (x+1), curinsum[act[i]]++;
for(int i = 1; i <= x; i++){
pair<int,int> bst; long double best = INF;
pair<int,int> bst1;
for(auto y : act){
if(y.second == -1) continue;
// buying this
if(tot[y] == curinb[y]) continue;
// can make the transition
if(tot[y] == curinb[y] + curinsum[y]){
// retreat from the sum
long double cur = dp[i-1] - 1.0*y.first/(x+1) + 1.0*y.second/i; // now take the other minimum(just bruteforce for now)
for(auto z : tot){
if(z.second == curinb[z.first] + curinsum[z.first]) continue;
long double tmp = cur + 1.0*z.first.first/(x+1);
if(tmp < best){
best = tmp;
bst = y;
bst1 = z.first;
}
}
}
else{
long double tmp = dp[i-1] + 1.0*y.second/(i);
if(tmp < best){
best = tmp;
bst = y;
bst1 = {-1,-1};
}
}
}
if(best == INF) continue;
curinb[bst]++;
if(bst1.first != -1) curinsum[bst]--,curinsum[bst1]++;
dp[i] = best;
}
// cerr<<dp[x]<<" ";
ans = min(ans, dp[x]); // having bought x collaborators
}
cout<<ans<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
756 KB |
Output is correct |
| 5 |
Correct |
438 ms |
800 KB |
Output is correct |
| 6 |
Execution timed out |
2531 ms |
788 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
756 KB |
Output is correct |
| 5 |
Correct |
438 ms |
800 KB |
Output is correct |
| 6 |
Execution timed out |
2531 ms |
788 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
500 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Incorrect |
0 ms |
600 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
500 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Incorrect |
0 ms |
600 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
500 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Incorrect |
0 ms |
600 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2517 ms |
548 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
756 KB |
Output is correct |
| 5 |
Correct |
438 ms |
800 KB |
Output is correct |
| 6 |
Execution timed out |
2531 ms |
788 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
