UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#152030#8. 小w、小j和小zLightningUZ0565ms1996kbC++111.7kb2022-07-30 18:32:122022-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