ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#143339 | #8. 小w、小j和小z | Xiao_mo | 0 | 36ms | 1256kb | C++ | 1.5kb | 2021-11-17 20:54:41 | 2021-11-17 20:54:42 |
answer
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define inf 1e8
#define rg register
using namespace std;
const int N=1e5+10;
inline ll read(){
register ll s=0,f=0;
register char ch=getchar();
while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
while(isdigit(ch)) s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return f?-s:s;
}
inline void write(ll x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
int n,k;
struct data{
int p,v;
}a[N];
struct qj{
double l,r;
}b[N];
inline bool cmp(qj a,qj b){
if(a.r==b.r)return a.l<b.l;
return a.r<b.r;
}
inline bool check(double x){
for(int i=1;i<=n;i++){
if(a[i].v>=0)b[i]={a[i].p,a[i].p+x*a[i].v};
else b[i]={a[i].p+x*a[i].v,a[i].p};
}
sort(b+1,b+1+n,cmp);
// for(int i=1;i<=n;i++){
// printf("l=%.5lf r=%.5lf\n",b[i].l,b[i].r);
// }
int cnt=1;
double ls=b[1].r;
for(int i=2;i<=n;i++){
if(ls<b[i].l)cnt++,ls=b[i].r;
}
// printf("x=%.5lf ",x);
// printf("%d\n",cnt);
if(n-cnt<=k)return 1;
return 0;
}
int main() {
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
n=read(),k=read();
for(int i=1;i<=n;i++)a[i].p=read(),a[i].v=read();
double l=0,r=2e9,ans;
while(r-l>=0.000000001){
double mid=(l+r)/2;
if(check(mid))ans=mid,l=mid;
else r=mid;
}
if(ans>=2e9-0.000001)printf("Forever");
else printf("%.4lf",ans);
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 1208kb
input:
20 10 -715624307 -28629151 957936621 17210368 -753657459 59049 -40974960 5153632 -402454312 -3450252...
output:
3.3174
result:
wrong answer expected 11.3999000000, found 3.3174000000
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 1ms
memory: 1212kb
input:
200 10 -487405787 3200000 725249085 28629151 -671026855 -4084101 38046635 45435424 -188495128 643634...
output:
0.0028
result:
wrong answer expected 0.0039000000, found 0.0028000000
Subtask #3:
score: 0
Skipped
Subtask #4:
score: 0
Wrong Answer
Test #18:
score: 15
Accepted
time: 12ms
memory: 1256kb
input:
2000 10 882856800 -387420489 866607093 -134217728 481381898 1 -488180557 1953125 -783185249 -19683 -...
output:
0.0002
result:
ok answer is 0.0001000000
Test #19:
score: 0
Accepted
time: 12ms
memory: 1252kb
input:
2000 10 882856800 -177147 866607093 -48828125 481381898 1 -488180557 48828125 -783185249 -362797056 ...
output:
0.0001
result:
ok answer is 0.0001000000
Test #20:
score: -15
Wrong Answer
time: 11ms
memory: 1252kb
input:
2000 10 882856800 -1 866607093 -396 481381898 21 -488180557 6 -783185249 -10 -816111307 -33761 99248...
output:
2.6194
result:
wrong answer expected 2.6237000000, found 2.6194000000
Subtask #5:
score: 0
Skipped
Subtask #6:
score: 0
Skipped