ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#138325 | #8. 小w、小j和小z | int32 | 10 | 12ms | 1404kb | C++11 | 801b | 2021-09-20 12:27:19 | 2021-09-20 12:27:20 |
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const long double inf=INT_MAX;
typedef long double ldb;
const ldb eps=1e-7;
int n, k;ldb l, r=inf, mid;
struct pep{ldb pos, vel;
bool operator <(const pep& p) const
{return pos<p.pos;}}a[N];ldb b[N];
bool equal(const ldb& x, const ldb& y)
{return (x+eps>y)&&(x-eps<y);}
bool check(ldb t)
{int res=0;for(int i=1;i<=n;i++)
{ldb x=a[i].pos+a[i].vel*t;
if(!res||b[res]<x) b[++res]=x;
if(res&&equal(b[res],x)) continue;
int f=upper_bound(b+1,b+res+1,x)-b;
b[f]=x;}return res+k>=n;}
signed main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i].pos>>a[i].vel;
sort(a+1,a+n+1);
while(l+eps<r)
{mid=(l+r)/2.0;if(check(mid)) l=mid;else r=mid;}
if(equal(inf,r)) puts("Forever");
else printf("%.2Lf",l);
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 1312kb
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: 1312kb
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: 1316kb
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: 1312kb
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: 1276kb
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: 1ms
memory: 1316kb
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: 6ms
memory: 1404kb
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: 3ms
memory: 1400kb
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: 2ms
memory: 1400kb
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