ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#148673 | #8. 小w、小j和小z | CodingShark | 10 | 11ms | 1280kb | C++ | 1.0kb | 2022-07-15 09:45:51 | 2022-07-15 09:45:54 |
answer
#include <bits/stdc++.h>
using namespace std;
int n, k;
double rec[100005];
struct node
{
int p, v;
bool operator<(const node t) const
{
return p == t.p ? v > t.v : p < t.p;
}
} a[100005];
bool check(double x)
{
int ans = 0;
for (int i = 1; i <= n; i++)
{
double v = a[i].p + a[i].v * x;
int pos = lower_bound(rec + 1, rec + ans + 1, v) - rec;
rec[pos] = v, ans = max(ans, pos);
}
return n - ans <= k;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
#endif
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%d %d", &a[i].p, &a[i].v);
sort(a + 1, a + n + 1);
double l = 0, r = 1e9;
while (r - l > 1e-6)
{
double mid = (l + r) / 2.0;
if (check(mid))
l = mid;
else
r = mid;
}
if (l > 1e8)
puts("Forever");
else
printf("%.2lf", l);
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 1260kb
input:
20 10 -715624307 -28629151 957936621 17210368 -753657459 59049 -40974960 5153632 -402454312 -3450252...
output:
11.40
result:
ok answer is 11.3999000000
Test #2:
score: 0
Accepted
time: 0ms
memory: 1256kb
input:
20 7 -715624307 -310 957936621 3 -753657459 1 -40974960 5 -402454312 -7424 874144191 -4 -227392025 7...
output:
5850568.50
result:
ok answer is 5850568.5000000000
Test #3:
score: 0
Accepted
time: 0ms
memory: 1260kb
input:
20 4 -715624307 -1 957936621 3 -753657459 6 -40974960 1 -402454312 -1 874144191 -2 -227392025 9 -808...
output:
3926260.00
result:
ok answer is 3926260.0000000000
Test #4:
score: 0
Accepted
time: 0ms
memory: 1260kb
input:
20 6 -715624307 -1 957936621 3 -753657459 1 -40974960 1 -402454312 -119 874144191 -1 -227392025 359 ...
output:
9635550.83
result:
ok answer is 9635550.8333000001
Test #5:
score: 0
Accepted
time: 0ms
memory: 1200kb
input:
20 10 -715624307 740210959 -955556582 -615695756 -24759231 771301784 -80855559 560021841 -892686343 ...
output:
Forever
result:
ok OK, forever!
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 0ms
memory: 1252kb
input:
200 10 -487405787 3200000 725249085 28629151 -671026855 -4084101 38046635 45435424 -188495128 643634...
output:
0.00
result:
wrong answer expected 0.0039000000, found 0.0000000000
Subtask #3:
score: 0
Skipped
Subtask #4:
score: 0
Wrong Answer
Test #18:
score: 15
Accepted
time: 4ms
memory: 1280kb
input:
2000 10 882856800 -387420489 866607093 -134217728 481381898 1 -488180557 1953125 -783185249 -19683 -...
output:
0.00
result:
ok answer is 0.0001000000
Test #19:
score: 0
Accepted
time: 4ms
memory: 1280kb
input:
2000 10 882856800 -177147 866607093 -48828125 481381898 1 -488180557 48828125 -783185249 -362797056 ...
output:
0.00
result:
ok answer is 0.0001000000
Test #20:
score: -15
Wrong Answer
time: 3ms
memory: 1280kb
input:
2000 10 882856800 -1 866607093 -396 481381898 21 -488180557 6 -783185249 -10 -816111307 -33761 99248...
output:
2.62
result:
wrong answer expected 2.6237000000, found 2.6200000000
Subtask #5:
score: 0
Skipped
Subtask #6:
score: 0
Skipped