| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1268535 | lambd47 | Let's Win the Election (JOI22_ho_t3) | C++20 | 0 ms | 0 KiB |
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define pii pair<int,int>
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
const int MOD=1e9+7;
void solve() {
int n,m;
cin>>n>>m;
vector<pii> vec(n);
L(i,0,n-1){
cin>>vec[i].first>>vec[i].second;
if(vec[i].second==-1)vec[i].second=MOD;
}
sort(all(vec),[&](pii a, pii b){
if(a.second==b.second)return a.first<b.first;
return a.second<b.second;
});
auto testa=[&](int k)->double{
vector<vector<double>> dp(k+1,vector<double> (m-k+1,(double)MOD));
dp[0][0]=0;
L(i,0,n-1){
R(j,k,0){
R(f,m-k,0){
if(j!=k && vec[i].second!=MOD)dp[j+1][f]=min(dp[j+1][f],dp[j][f]+(double)vec[i].second/(j+1));
if(f!=(m-k))dp[j][f+1]=min(dp[j][f+1],dp[j][f]+(double)vec[i].first/(k+1));
}
}
}
return dp[k][m-k];
};
cout<<fixed<<setprecision(8);
double resp=(double) MOD;
cout<<resp<<"\n";
}
int32_t main() {
std::cin.tie(0)->sync_with_stdio(0);
std::cin.exceptions(std::cin.failbit);
int T = 1;
// std::cin >> T;
while(T--) {
solve();
}
return 0;
}