#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mkp make_pair
#define PH push
#define PB push_back
#define REP(i,N) for( int i = 0; i < (N); ++i )
#define FOR(i,a,b) for( int i = (a); i <= (b); ++i )
#define ALL(x) begin(x), end(x)
#define MEM(x) memset(x, 0, sizeof(x))
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T>
using V=vector<T>;
#define double float
void solve() {
int N, K; cin >> N >> K;
V<pll> vc(N+1);
const ll INF = 1e18;
FOR(i,1,N) cin >> vc[i].F >> vc[i].S;
for( auto &i : vc ) if( i.S == -1 ) i.S = INF;
sort( vc.begin()+1, vc.end(), [&]( auto&a, auto&b) {
return a.S < b.S;
});
//V<V<V<double>>> dp( 2, V<V<double>>( K+1, V<double>(K+1, 0) ));
V<V<double>> dp(K+1,V<double>(K+1,0));
//double dp[ N+1 ][ K+1 ][ K+1 ];
auto init = [&]() {
for( auto &i : dp ) for( auto &j : i )/* for( auto &k : j ) */
k = INF;
dp[ 1 ][ 0 ] = 0;
};
auto do_dp = [&](int p) {
double ans=INF;
init();
for( int i = 1; i <= N; ++i ) {
for( int j = K; j>=0; --j ) {
for( int k = K; k >=0; --k ) {
dp[ j ][ k ] = min(
( j == 1 ? INF : dp[j-1][k-1]+(1.0f*vc[i].S/(j-1)) ),
dp[j][k-1] + (1.0f*vc[i].F/p),
);
}
}
}
//fprintf(stderr, "ans:(%.16lf), p(%d)\n", ans, p );
ans = min( dp[N&1][p][K], ans );
return ans;
};
int l = 1, r = K;
double ans = INF;
while( r-l > 4 ) {
int l1 = (l+l+r)/3, l2 = (l+r+r)/3;
double ans1 = do_dp(l1);
double ans2 = do_dp(l2);
ans = min( {ans,ans1,ans2} );
if( ans1 > ans2 )
l=l1;
else
r=l2;
}
for( int i = l; i<=r; ++i )
ans = min( ans, do_dp(i));
cout << fixed << setprecision(10);
cout << ans << '\n';
}
int main() {
int T = 1;
#ifdef LOCAL
freopen( "input.txt", "r", stdin);
freopen( "output.txt", "w", stdout );
cin >> T;
#else
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
while(T--) solve();
}
Compilation message
Main.cpp: In lambda function:
Main.cpp:39:4: error: 'k' was not declared in this scope
39 | k = INF;
| ^
Main.cpp:38:34: warning: unused variable 'j' [-Wunused-variable]
38 | for( auto &i : dp ) for( auto &j : i )/* for( auto &k : j ) */
| ^
Main.cpp: In lambda function:
Main.cpp:52:6: error: expected primary-expression before ')' token
52 | );
| ^
Main.cpp:57:24: error: invalid types '__gnu_cxx::__alloc_traits<std::allocator<float>, float>::value_type {aka float}[int]' for array subscript
57 | ans = min( dp[N&1][p][K], ans );
| ^
