This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (b); i >= (a); i --)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define REPD(i, a) for (int i = (a) - 1; i >= 0; --i)
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
/*
Phu Trong from Nguyen Tat Thanh High School for gifted student
*/
template <class X, class Y>
bool minimize(X &x, const Y &y){
X eps = 1e-9;
if (x > y + eps) {x = y; return 1;}
return 0;
}
template <class X, class Y>
bool maximize(X &x, const Y &y){
X eps = 1e-9;
if (x + eps < y) {x = y; return 1;}
return 0;
}
#define MAX 505
int N, K;
double A[MAX], B[MAX];
double dp[MAX][MAX], cost[MAX][MAX];
void process(void){
cin >> N >> K;
for (int i = 1; i <= N; ++i){
cin >> A[i] >> B[i];
if(B[i] == -1) B[i] = 1e9;
}
vector<int> order(N + 1);
iota(order.begin(), order.end(), 0);
sort(order.begin() + 1, order.end(), [&](int i, int j){
return B[i] < B[j];
});
vector<double> vals;
FOR(i, 0, N) FOR(j, 0, N) cost[i][j] = 1e9;
for (int i = N; i >= 1; --i){
vals.push_back(A[order[i]]);
sort(vals.begin(), vals.end());
double sm = 0;
cost[i][0] = 0;
for (int j = 0; j < (int)vals.size(); ++j){
sm += vals[j];
cost[i][j + 1] = sm;
}
}
double ans = cost[1][K];
for (int tak = 0; tak <= K; ++tak){
for (int i = 0; i <= K; ++i){
for (int j = 0; j <= K; ++j){
dp[i][j] = 1e9;
}
}
dp[0][0] = 0;
for (int i = 1; i <= K; ++i){
for (int j = 0; j <= i; ++j){
dp[i][j] = dp[i - 1][j] + (double)A[order[i]] / (double)(tak + 1);
if(j > 0)
minimize(dp[i][j], dp[i - 1][j - 1] + (double)B[order[i]] / (double)(j));
if(j == tak){
int need = K - i;
minimize(ans, dp[i][j] + (double)cost[i + 1][need] / (double)(tak + 1));
}
}
}
}
cout << setprecision(10) << fixed << ans;
}
signed main(){
#define name "Whisper"
cin.tie(nullptr) -> sync_with_stdio(false);
//freopen(name".inp", "r", stdin);
//freopen(name".out", "w", stdout);
process();
return (0 ^ 0);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |