#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] ;
ll 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;
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(8) << 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
Main.cpp: In function 'int main()':
Main.cpp:112:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
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".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
2 ms |
736 KB |
Output is correct |
7 |
Correct |
11 ms |
1348 KB |
Output is correct |
8 |
Correct |
30 ms |
1752 KB |
Output is correct |
9 |
Correct |
78 ms |
2340 KB |
Output is correct |
10 |
Correct |
25 ms |
1748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
2 ms |
736 KB |
Output is correct |
7 |
Correct |
11 ms |
1348 KB |
Output is correct |
8 |
Correct |
30 ms |
1752 KB |
Output is correct |
9 |
Correct |
78 ms |
2340 KB |
Output is correct |
10 |
Correct |
25 ms |
1748 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
6 ms |
860 KB |
Output is correct |
13 |
Correct |
6 ms |
852 KB |
Output is correct |
14 |
Correct |
6 ms |
852 KB |
Output is correct |
15 |
Correct |
52 ms |
1620 KB |
Output is correct |
16 |
Correct |
48 ms |
1620 KB |
Output is correct |
17 |
Correct |
35 ms |
1620 KB |
Output is correct |
18 |
Correct |
145 ms |
2448 KB |
Output is correct |
19 |
Correct |
116 ms |
2320 KB |
Output is correct |
20 |
Correct |
85 ms |
2320 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
170 ms |
2320 KB |
Output is correct |
2 |
Correct |
162 ms |
2336 KB |
Output is correct |
3 |
Correct |
156 ms |
2444 KB |
Output is correct |
4 |
Correct |
214 ms |
2320 KB |
Output is correct |
5 |
Correct |
162 ms |
2328 KB |
Output is correct |
6 |
Correct |
158 ms |
2268 KB |
Output is correct |
7 |
Correct |
158 ms |
2304 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
2 ms |
736 KB |
Output is correct |
7 |
Correct |
11 ms |
1348 KB |
Output is correct |
8 |
Correct |
30 ms |
1752 KB |
Output is correct |
9 |
Correct |
78 ms |
2340 KB |
Output is correct |
10 |
Correct |
25 ms |
1748 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
6 ms |
860 KB |
Output is correct |
13 |
Correct |
6 ms |
852 KB |
Output is correct |
14 |
Correct |
6 ms |
852 KB |
Output is correct |
15 |
Correct |
52 ms |
1620 KB |
Output is correct |
16 |
Correct |
48 ms |
1620 KB |
Output is correct |
17 |
Correct |
35 ms |
1620 KB |
Output is correct |
18 |
Correct |
145 ms |
2448 KB |
Output is correct |
19 |
Correct |
116 ms |
2320 KB |
Output is correct |
20 |
Correct |
85 ms |
2320 KB |
Output is correct |
21 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |