| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 995958 | vyshniak_n | Let's Win the Election (JOI22_ho_t3) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#pragma optimize("Ofast")
//#pragma optimize("unroll-loops")
//#pragma traget("avx,avx2")
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define el '\n'
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define point pair <ll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
#include <random>
mt19937 rnd(time(0));
const ll INF = 1e18 + 10;
const ll inf = 1e9 + 10;
const ll N = 5e2 + 10;
const ll mod = 998244353;
const ll LOG = 20;
const ll K = 1e3 + 20;
double dp[N][N][N];
ll n, k, a[N], b[N], order[N];
// dp is (pos, cooperator, votes)
ld calc(ll x) {
for (ll i = 1; i <= n; i++) {
for (ll j = 0; j <= x; j++) {
for (ll votes = 0; votes <= n - j; votes++) {
dp[i][j][votes + j] = dp[i - 1][j][votes + j];
if (j != 0 && b[order[i]] != inf) {
dp[i][j][votes + j] = min(dp[i][j][votes + j],
dp[i - 1][j - 1][votes + j - 1] + (ld)b[order[i]] / (ld)(j));
}
if (votes != 0) {
dp[i][j][votes + j] = min(dp[i][j][votes + j],
dp[i - 1][j][votes + j - 1] + (ld)a[order[i]] / (ld)(x + 1));
}
}
}
}
ld res = dp[n][x][k];
for (ll i = 1; i <= n; i++)
for (ll j = 0; j <= x; j++)
for (ll votes = 0; votes < n - j; votes++)
dp[i][j][votes + j] = inf;
return res;
}
void solve() {
cin >> n >> k;
for (ll i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
if (b[i] == -1)
b[i] = inf;
}
for (ll i = 1; i <= n; i++)
order[i] = i;
sort(order + 1, order + n + 1, [&](const ll &i, const ll &j) -> bool {
if (b[i] == b[j])
return a[i] < a[j];
return b[i] < b[j];
});
for (ll i = 0; i <= n; i++)
for (ll j = 0; j <= n; j++)
for (ll votes = 0; votes <= n; votes++)
dp[i][j][votes] = inf;
dp[0][0][0] = 0;
ld ans = inf;
for (ll i = 0; i <= k; i++)
ans = min(ans, calc(i));
cout << fixed << setprecision(10) << ans << el;
return;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int tests = 1;
//cin >> tests;
while (tests--)
solve();
return 0;
}
/*
*/