#ifdef LOCAL
//#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <random>
#ifndef LOCAL
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#endif
using namespace std;
using ll = long long;
using ld = long double;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
mt19937_64 mt(418);
void solve();
void init();
int32_t main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
#endif
// srand(time(0));
init();
cout << fixed << setprecision(20);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
void init() {}
int lay = 1;
bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
if (a.y < b.y) {
return true;
}
if (a.y > b.y) {
return false;
}
return a.x < b.x;
}
void solve() {
int n, k;
cin >> n >> k;
vector<pair<int, int>> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i].x >> a[i].y;
if (a[i].y == -1) {
a[i].y = INT32_MAX / 2;
}
}
double ans = 2e18;
vector<vector<vector<double>>> dp(n + 1, vector<vector<double>>(k + 1, vector<double>(n + 1, 2e18)));
// for (int ll = 0; ll <= n; ll++) {
sort(all(a), cmp)
for (int i = 0; i < n; i++) {
for (int j = 0; j <= k; j++) {
for (int l = 0; l <= n; l++) {
dp[i + 1][j][l] = 2e18;
}
}
}
dp[0][0][0] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= k; j++) {
for (int l = 0; l <= n; l++) {
dp[i + 1][j][l] = min(dp[i + 1][j][l], dp[i][j][l]);
if (j > 0) {
dp[i + 1][j][l] = min(dp[i + 1][j][l], dp[i][j - 1][l] + a[i].x / (double)(l + 1));
if (l > 0) {
dp[i + 1][j][l] = min(dp[i + 1][j][l], dp[i][j - 1][l - 1] + a[i].y / (double)l);
}
}
}
}
}
for (int i = 0; i <= n; i++) {
ans = min(ans, dp[n][k][i]);
}
lay++;
// }
cout << ans << '\n';
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:68:26: error: expected ';' before 'for'
68 | sort(all(a), cmp)
| ^
| ;
69 | for (int i = 0; i < n; i++) {
| ~~~
Main.cpp:69:25: error: 'i' was not declared in this scope
69 | for (int i = 0; i < n; i++) {
| ^
