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>
#define ll long long
#define ld long double
#define pb push_back
#define pll pair<ll, int>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 5e2+5;
const int M = 8;
const int mod = 998244353;
const int base = 350;
const int inf = 1e9;
int m, n, k, t, c[N], d[N] ;
int ans, tong, b[N], a[N];
vector<int> adj[N];
string s;
int r, sz, ntime;
struct BIT
{
int n;
vector<int> fe;
BIT(){}
void init(int _n)
{
n = _n;
fe.assign(n+1, 0);
}
void add(int id, int x)
{
++id;
for(; id <= n; id += id & -id)fe[id] += x;
}
int get(int id)
{
++id;
id = min(id, n);
if(id <= 0)return 0;
int total = 0;
for(; id; id -= id & -id)total += fe[id];
return total;
}
int get(int l, int r)
{
return get(r) - get(l-1);
}
}bit[3];
void dfs(int u, int p = 0)
{
int mx = 0;
d[u] = 1;
for(int v: adj[u])
{
if(v == p || b[v])continue;
dfs(v, u);
d[u] += d[v];
mx = max(d[v], mx);
}
mx = max(mx, sz-d[u]);
if(mx*2 <= sz)r = u;
}
pii p[N];
double dp[N][N];
bool cmp(const pii& x, const pii& y)
{
if(x.se == y.se)return x.fi < y.fi;
if(x.se == -1 || y.se == -1)return x.se > y.se;
return x.se < y.se;
}
void add(double& x, double y)
{
if(x > y)x = y;
}
void sol()
{
cin >> n >> k;
for(int i = 1; i <= n; i ++)cin >> p[i].fi >> p[i].se;
sort(p+1, p+1+n, cmp);
double res = inf;
for(int i = 0; i <= k; i ++)
{
for(int j = i+1; j <= n; j ++)a[j-i] = p[j].fi;
sort(a+1, a+n-i+1);
for(int j = 1; j <= k-i; j ++)b[i] += a[j];
}
for(int x = 0; x <= k; x ++)
{
for(int j = 1; j <= x; j ++)dp[0][j] = inf;
add(res, dp[0][x]+b[0]);
for(int i = 1; i <= k; i ++)
{
for(int j = 0; j <= x; j ++)
{
dp[i][j] = inf;
add(dp[i][j], dp[i-1][j] + p[i].fi*1.0/(x+1));
if(j && p[i].se != -1)add(dp[i][j], dp[i-1][j-1] + p[i].se*1.0/j);
}
add(res, dp[i][x]+b[i]*1.0/(x+1));
}
}
cout << fixed << setprecision(5) << res;
}
int main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
#define task "test"
if(fopen(task".inp", "r"))
{
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int test = 1;
//cin >> test;
while(test -- > 0)sol();
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:113:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
113 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:114:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |