/*
IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
#define F first
#define S second
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) ((ll)x.size())
#define all(x) (x).begin(),(x).end()
#define kill(x) cout << x << '\n', exit(0);
#define fuck(x) cout << "(" << #x << " , " << x << ")" << endl
#define endl '\n'
const int N = 3e5+23, lg = 18;
ll Mod = 1e9+7; //998244353;
inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
ll ans = 1;
a=MOD(a, mod);
while (b) {
if (b & 1) ans = MOD(ans*a, mod);
b >>= 1;
a = MOD(a*a, mod);
}
return ans;
}
int n, k, A[N], B[N];
ld dp[505][505], pd[505][505];
pair<ld, ld> x[N], y[N];
ld check(int mid) {
for(int i=0; i<=n; i++) fill(dp[i], dp[i]+k+2, 1e9);
ld ans = 1e9;
dp[0][0] = 0;
for(int i=1; i<=n; i++) {
for(int j=0; j<=i&&j<=k; j++) {
if(j>0) dp[i][j] = min(dp[i][j], dp[i-1][j-1]+x[i].F/(ld)(j));
dp[i][j] = min(dp[i][j], dp[i-1][j]+x[i].S/(ld)(mid+1));
}
if(k>=i) {
ans = min(ans, dp[i][mid]+pd[i+1][k-i]/(ld)(mid+1));
}
}
ans = min(ans, pd[1][k]);
return ans;
}
int main () {
ios_base::sync_with_stdio(false), cin.tie(0);
cout<<fixed<<setprecision(10);
cin>>n>>k;
for(int i=1; i<=n; i++) {
cin>>A[i]>>B[i];
if(B[i]==-1) B[i] = 1000000;
x[i] = {B[i], A[i]};
}
sort(x+1, x+n+1);
for(int i=1; i<=n+1; i++) fill(pd[i], pd[i]+k+2, 1e9);
pd[n+1][0] = 0;
for(int i=n; i>=1; i--) {
for(int j=0; j<=k; j++) {
pd[i][j] = pd[i+1][j];
if(j > 0) pd[i][j] = min(pd[i][j], pd[i+1][j-1] + x[i].S);
}
}
ld res = 1e9;
int l=0, r=k;
while(r-l>1) {
int mid = (l+r)/2;
if(check(mid) > check(mid+1)) {
res=min(res, check(mid+1));
r=mid;
} else {
res=min(res, check(mid));
l=mid;
}
}
//for(int i=0; i<=k; i++) res = min(res, check(i)), cout<<check(i)<<endl;
cout<<res;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
12760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
