ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#152030 | #8. 小w、小j和小z | LightningUZ | 0 | 565ms | 1996kb | C++11 | 1.7kb | 2022-07-30 18:32:12 | 2022-07-30 18:32:14 |
answer
#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define F(i,l,r) for(int i=(l);i<=(r);++i)
#define D(i,r,l) for(int i=(r);i>=(l);--i)
#define MEM(x,a) memset(x,a,sizeof(x))
int I() {char c=getchar(); int x=0; int f=1; while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar(); while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return ((f==1)?x:-x);}
#define re double
#define eps 1e-8
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define vpii vector<pii>
#define fi first
#define se second
#define sz(x) ((int)x.size())
#define al(x) x.begin(),x.end()
int n,k; pii a[N];
re b[N]; re d[N]; int bb[N];
int t[N],f[N];
void ad(int p,int x){for(int i=p;i<=n;i+=(i&(-i)))t[i]=max(t[i],x);}
int qr(int p){int s=0;for(int i=p;i;i-=(i&(-i)))s=max(s,t[i]);return s;}
bool cxk(re ti)
{
F(i,1,n)b[i]=a[i].fi+ti*a[i].se;
// F(i,1,n)d[i]=b[i];sort(d+1,d+n+1);
// F(i,1,n)bb[i]=lower_bound(d+1,d+n+1,b[i])-d;
// printf("b: ");F(i,1,n)printf("%.5lf ",b[i]); puts("");
// printf("bb: ");F(i,1,n)printf("%d ",bb[i]); puts("");
// F(i,0,n) t[i]=0;
// F(i,1,n) f[i]=qr(bb[i]-1)+1,ad(bb[i],f[i]);
F(i,1,n){f[i]=1; F(j,1,i-1)if(b[j]<=b[i]-0.001)f[i]=max(f[i],f[j]+1);}
int ans=0;F(i,1,n)ans=max(ans,f[i]);
return ans>=n-k;
}
void flandre()
{
n=I(),k=I();
F(i,1,n)a[i]={I(),I()};
sort(a+1,a+n+1);
re l=0,r=2e9;
while(r-l>=0.00001)
{
re mid=(l+r)/2.0;
if(cxk(mid))l=mid;
else r=mid;
}
// printf("%.3lf\n",l);
if(l>2e9) puts("Forever");
else printf("%.4lf\n",l);
}
int main()
{
int t=1;
while(t-->0){flandre();}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 1980kb
input:
20 10 -715624307 -28629151 957936621 17210368 -753657459 59049 -40974960 5153632 -402454312 -3450252...
output:
0.1795
result:
wrong answer expected 11.3999000000, found 0.1795000000
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 3ms
memory: 1984kb
input:
200 10 -487405787 3200000 725249085 28629151 -671026855 -4084101 38046635 45435424 -188495128 643634...
output:
0.0000
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: 183ms
memory: 1996kb
input:
2000 10 882856800 -387420489 866607093 -134217728 481381898 1 -488180557 1953125 -783185249 -19683 -...
output:
0.0000
result:
ok answer is 0.0001000000
Test #19:
score: 0
Accepted
time: 184ms
memory: 1996kb
input:
2000 10 882856800 -177147 866607093 -48828125 481381898 1 -488180557 48828125 -783185249 -362797056 ...
output:
0.0000
result:
ok answer is 0.0001000000
Test #20:
score: -15
Wrong Answer
time: 194ms
memory: 1996kb
input:
2000 10 882856800 -1 866607093 -396 481381898 21 -488180557 6 -783185249 -10 -816111307 -33761 99248...
output:
0.0000
result:
wrong answer expected 2.6237000000, found 0.0000000000
Subtask #5:
score: 0
Skipped
Subtask #6:
score: 0
Skipped