#include <bits/stdc++.h>
#define int long long
#define inf (1 << 30)
#define ld long double
using namespace std;
const int N = 113;
int a[N], b[N], s[N];
int id_x[N], id_y[N];
int vid_x[N], vid_y[N];
struct Pair{
int a, b, id;
Pair() = default;
Pair(int _a, int _b, int _i) : a(_a), b(_b), id(_i){};
};
vector<Pair> vp;
long double dp[N][N][N];
int cnt[N][N];
int32_t main(){
int n, K;
cin >> n >> K;
for(int i = 0; i < n; i++){
cin >> a[i] >> b[i];
b[i] = (b[i] == -1) ? inf : b[i];
vp.push_back({a[i], b[i], i});
}
sort(vp.begin(), vp.end(), [](Pair x, Pair y){
return x.a < y.a || x.a == y.a && x.b < y.b;
});
for(int i = 0; i < n; i++){
id_x[i] = vp[i].id;
vid_x[vp[i].id] = i;
}
sort(vp.begin(), vp.end(), [](Pair x, Pair y){
return x.b < y.b || x.b == y.b && x.a < y.a;
});
for(int i = 0; i < n; i++){
id_y[i] = vp[i].id;
vid_y[vp[i].id] = i;
}
/*
for(int i = 0; i < n; i++){
cout << vid_x[i] << ' ' << vid_y[i] << ' ' << id_x[i] << ' ' << id_y[i] << endl;
}
*/
for(int i = 0; i < n; i++){
cnt[vid_x[i] + 1][vid_y[i] + 1] = 1;
}
/*
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++){
cout << cnt[i][j] << ' ';
}
cout << endl;
}
cout << endl;
*/
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cnt[i][j] = cnt[i - 1][j] + cnt[i][j - 1] + cnt[i][j] - cnt[i - 1][j - 1];
}
}
/*
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++){
cout << cnt[i][j] << ' ';
}
cout << endl;
}
cout << endl;
for(int i = 0; i < n; i++){
cout << a[id_x[i]] << ' ';
}
cout << endl;
for(int i = 0; i < n; i++){
cout << b[id_y[i]] << ' ';
}
cout << endl;
*/
long double ans = inf;
for(int l = 0; l <= n; l++){
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++){
for(int k = 0; k <= n; k++){
dp[i][j][k] = inf;
}
}
}
dp[0][0][0] = 0;
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++){
for(int k = 0; k <= n; k++){
if(i > 0){
if(vid_y[id_x[i - 1]] >= j){
dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k]);
}
}
if(j > 0){
if(vid_x[id_y[j - 1]] < i){
dp[i][j][k] = min(dp[i][j][k], dp[i][j - 1][k] - (vid_y[id_x[i - 1]] < j ? (ld) a[id_x[i - 1]] / (l + 1) : 0));
}else{
if(k > 0 && b[id_y[j - 1]] != inf){
dp[i][j][k] = min(dp[i][j][k], dp[i][j - 1][k - 1] + (ld) b[id_y[j - 1]] / k - (vid_y[id_x[i - 1]] < j ? (ld) a[id_x[i - 1]] / (l + 1) : 0));
}
}
}
}
if(i + j - cnt[i][j] == K){
ans = min(ans, dp[i][j][l]);
}
}
}
}
/*
for(int k = 0; k <= n; k++){
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++){
cout << dp[i][j][k] << ' ';
}
cout << endl;
}
cout << endl;
}
*/
cout << fixed << setprecision(15) << ans << endl;
}
Compilation message
Main.cpp: In lambda function:
Main.cpp:32:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
32 | return x.a < y.a || x.a == y.a && x.b < y.b;
| ~~~~~~~~~~~^~~~~~~~~~~~
Main.cpp: In lambda function:
Main.cpp:41:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
41 | return x.b < y.b || x.b == y.b && x.a < y.a;
| ~~~~~~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
