ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#159019 | #8. 小w、小j和小z | wuzr | 0 | 24ms | 2156kb | C++ | 1.2kb | 2022-08-28 18:55:18 | 2022-08-28 18:55:19 |
answer
#include<bits/stdc++.h>
using namespace std;
#define re register
#define rep(i,a,b) for(ll i(a);i<=b;++i)
#define per(i,a,b) for(ll i(a);i>=b;--i)
#define ll long long
#define swap(x,y) x^=y^=x^=y
#define y1 yyy1
#define int ll
struct node {
int p, v;
} a[100005];
int n, k;
int dp[100005];
double pos[100005], low[100005];
bool ck(double x) {
rep(i, 1, n) pos[i] = a[i].p + a[i].v * x;
memset(dp, 0, sizeof dp);
int mx = 0;
low[0] = -9e18;
rep(i, 1, n) {
dp[i] = upper_bound(low, low + mx + 1, pos[i] - 1e-7) - low;
if (dp[i] > mx) {
mx = dp[i];
low[mx] = pos[i];
} else low[dp[i]] = max(low[dp[i]], pos[i]);
}
return mx + k >= n;
}
bool cmp(node x, node y) {
if (x.p == y.p) return x.v > y.v;
else return x.p < y.p;
}
signed main() {
ios::sync_with_stdio(0);
cin >> n >> k;
rep(i, 1, n) cin >> a[i].p >> a[i].v;
sort(a + 1, a + n + 1, cmp);
int t = 1;
rep(i, 2, n) {
if (a[i].p == a[t].p && a[i].v == a[t].v) k--;
else a[++t] = a[i];
}
n = t;
double l = 0, r = 2.5e9;
while (l + 1e-7 < r) {
double mid = (l + r) / 2;
if (ck(mid)) l = mid;
else r = mid;
}
double ans = (l + r) / 2;
if (ans > 2.4e9) puts("Forever");
else printf("%.6lf", ans);
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 2088kb
input:
20 10 -715624307 -28629151 957936621 17210368 -753657459 59049 -40974960 5153632 -402454312 -3450252...
output:
1.264558
result:
wrong answer expected 11.3999000000, found 1.2645580000
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 20
Accepted
time: 0ms
memory: 2096kb
input:
200 10 -487405787 3200000 725249085 28629151 -671026855 -4084101 38046635 45435424 -188495128 643634...
output:
0.003057
result:
ok answer is 0.0039000000
Test #7:
score: 0
Accepted
time: 3ms
memory: 2092kb
input:
200 10 -487405787 1 725249085 65536 -671026855 -100000000 38046635 1679616 -188495128 6561 -73172885...
output:
0.004186
result:
ok answer is 0.0041000000
Test #8:
score: -20
Wrong Answer
time: 4ms
memory: 2100kb
input:
200 10 -487405787 3 725249085 2 -671026855 -6 38046635 5 -188495128 14 -731728859 12 -331220744 2 31...
output:
11602.228070
result:
wrong answer expected 14398.5188000000, found 11602.2280700000
Subtask #3:
score: 0
Skipped
Subtask #4:
score: 0
Wrong Answer
Test #18:
score: 15
Accepted
time: 6ms
memory: 2156kb
input:
2000 10 882856800 -387420489 866607093 -134217728 481381898 1 -488180557 1953125 -783185249 -19683 -...
output:
0.000167
result:
ok answer is 0.0001000000
Test #19:
score: 0
Accepted
time: 6ms
memory: 2156kb
input:
2000 10 882856800 -177147 866607093 -48828125 481381898 1 -488180557 48828125 -783185249 -362797056 ...
output:
0.000114
result:
ok answer is 0.0001000000
Test #20:
score: -15
Wrong Answer
time: 3ms
memory: 2152kb
input:
2000 10 882856800 -1 866607093 -396 481381898 21 -488180557 6 -783185249 -10 -816111307 -33761 99248...
output:
0.009964
result:
wrong answer expected 2.6237000000, found 0.0099640000
Subtask #5:
score: 0
Skipped
Subtask #6:
score: 0
Skipped