UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#152038#8. 小w、小j和小zLightningUZ803523ms1256kbC++111.7kb2022-07-30 18:37:542022-07-30 18:37:56

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; struct nd{int p,v;}a[N]; bool operator<(nd a,nd b){return a.p<b.p;}
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].p+ti*a[i].v;
    // 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=3e9;
    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: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 1220kb

input:

20 10
-715624307 -28629151
957936621 17210368
-753657459 59049
-40974960 5153632
-402454312 -3450252...

output:

11.3999

result:

ok answer is 11.3999000000

Test #2:

score: 0
Accepted
time: 0ms
memory: 1220kb

input:

20 7
-715624307 -310
957936621 3
-753657459 1
-40974960 5
-402454312 -7424
874144191 -4
-227392025 7...

output:

5850568.4997

result:

ok answer is 5850568.5000000000

Test #3:

score: 0
Accepted
time: 1ms
memory: 1216kb

input:

20 4
-715624307 -1
957936621 3
-753657459 6
-40974960 1
-402454312 -1
874144191 -2
-227392025 9
-808...

output:

3926259.9990

result:

ok answer is 3926260.0000000000

Test #4:

score: 0
Accepted
time: 0ms
memory: 1220kb

input:

20 6
-715624307 -1
957936621 3
-753657459 1
-40974960 1
-402454312 -119
874144191 -1
-227392025 359
...

output:

9635550.8332

result:

ok answer is 9635550.8333000001

Test #5:

score: 0
Accepted
time: 0ms
memory: 1156kb

input:

20 10
-715624307 740210959
-955556582 -615695756
-24759231 771301784
-80855559 560021841
-892686343 ...

output:

Forever

result:

ok OK, forever!

Subtask #2:

score: 20
Accepted

Test #6:

score: 20
Accepted
time: 0ms
memory: 1220kb

input:

200 10
-487405787 3200000
725249085 28629151
-671026855 -4084101
38046635 45435424
-188495128 643634...

output:

0.0039

result:

ok answer is 0.0039000000

Test #7:

score: 0
Accepted
time: 3ms
memory: 1216kb

input:

200 10
-487405787 1
725249085 65536
-671026855 -100000000
38046635 1679616
-188495128 6561
-73172885...

output:

0.0042

result:

ok answer is 0.0041000000

Test #8:

score: 0
Accepted
time: 3ms
memory: 1220kb

input:

200 10
-487405787 3
725249085 2
-671026855 -6
38046635 5
-188495128 14
-731728859 12
-331220744 2
31...

output:

14398.5189

result:

ok answer is 14398.5188000000

Test #9:

score: 0
Accepted
time: 3ms
memory: 1224kb

input:

200 10
-487405787 56
725249085 2
-671026855 -8
38046635 1
-188495128 252
-731728859 28
-331220744 2
...

output:

8320.3684

result:

ok answer is 8320.3684000000

Test #10:

score: 0
Accepted
time: 0ms
memory: 1224kb

input:

200 10
-487405787 11
725249085 8
-671026855 -1
38046635 1
-188495128 125
-731728859 106
-331220744 4...

output:

543.5187

result:

ok answer is 543.5186000000

Test #11:

score: 0
Accepted
time: 0ms
memory: 1160kb

input:

200 10
-584283703 -467650291
-389608337 -287739809
-372147316 -257836606
175915600 328991856
7355243...

output:

Forever

result:

ok OK, forever!

Subtask #3:

score: 15
Accepted

Test #12:

score: 15
Accepted
time: 0ms
memory: 1216kb

input:

200 50
-487405787 3200000
725249085 28629151
-671026855 -4084101
38046635 45435424
-188495128 643634...

output:

0.0359

result:

ok answer is 0.0359000000

Test #13:

score: 0
Accepted
time: 0ms
memory: 1216kb

input:

200 100
-487405787 690807104
725249085 2685619
-671026855 -18399744
38046635 862801408
-188495128 54...

output:

0.1288

result:

ok answer is 0.1288000000

Test #14:

score: 0
Accepted
time: 3ms
memory: 1224kb

input:

200 90
-487405787 3
725249085 2
-671026855 -6
38046635 5
-188495128 14
-731728859 12
-331220744 2
31...

output:

3184277.2307

result:

ok answer is 3184277.2307000002

Test #15:

score: 0
Accepted
time: 3ms
memory: 1224kb

input:

200 60
-487405787 56
725249085 2
-671026855 -8
38046635 1
-188495128 252
-731728859 28
-331220744 2
...

output:

572916.7619

result:

ok answer is 572916.7619000000

Test #16:

score: 0
Accepted
time: 3ms
memory: 1220kb

input:

200 30
-487405787 11
725249085 8
-671026855 -1
38046635 1
-188495128 125
-731728859 106
-331220744 4...

output:

7362.4506

result:

ok answer is 7362.4506000000

Test #17:

score: 0
Accepted
time: 3ms
memory: 1160kb

input:

200 75
-584283703 -510093529
-389608337 -734253121
-372147316 -257836606
175915600 -355171217
735524...

output:

Forever

result:

ok OK, forever!

Subtask #4:

score: 15
Accepted

Test #18:

score: 15
Accepted
time: 254ms
memory: 1252kb

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: 249ms
memory: 1248kb

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: 0
Accepted
time: 242ms
memory: 1248kb

input:

2000 10
882856800 -1
866607093 -396
481381898 21
-488180557 6
-783185249 -10
-816111307 -33761
99248...

output:

2.6237

result:

ok answer is 2.6237000000

Test #21:

score: 0
Accepted
time: 241ms
memory: 1248kb

input:

2000 10
882856800 -3
866607093 -2
481381898 12
-488180557 8639109
-783185249 -12
-816111307 -96
9924...

output:

0.0008

result:

ok answer is 0.0008000000

Test #22:

score: 0
Accepted
time: 244ms
memory: 1252kb

input:

2000 10
882856800 -1
866607093 -10
481381898 406927
-488180557 1
-783185249 -1483
-816111307 -8
9924...

output:

0.0003

result:

ok answer is 0.0003000000

Test #23:

score: 0
Accepted
time: 244ms
memory: 1192kb

input:

2000 10
784172079 808971860
81381899 71917076
-712636352 -738530531
-622770179 -640667385
119667134 ...

output:

Forever

result:

ok OK, forever!

Subtask #5:

score: 20
Accepted

Test #24:

score: 20
Accepted
time: 249ms
memory: 1252kb

input:

2000 200
882856800 -177147
866607093 -48828125
481381898 1
-488180557 48828125
-783185249 -362797056...

output:

0.0024

result:

ok answer is 0.0024000000

Test #25:

score: 0
Accepted
time: 274ms
memory: 1252kb

input:

2000 500
882856800 -46656
866607093 -1000000
481381898 64000000
-488180557 481890304
-783185249 -466...

output:

0.0056

result:

ok answer is 0.0056000000

Test #26:

score: 0
Accepted
time: 299ms
memory: 1252kb

input:

2000 1200
882856800 -2000376
866607093 -344472101
481381898 97336
-488180557 278445077
-783185249 -1...

output:

0.0330

result:

ok answer is 0.0330000000

Test #27:

score: 0
Accepted
time: 244ms
memory: 1256kb

input:

2000 900
882856800 -1
866607093 -40
481381898 2
-488180557 2
-783185249 -1
-816111307 -70227
9924839...

output:

313683.6663

result:

ok answer is 313683.6667000000

Test #28:

score: 0
Accepted
time: 245ms
memory: 1252kb

input:

2000 600
882856800 -1
866607093 -396
481381898 21
-488180557 6
-783185249 -10
-816111307 -33761
9924...

output:

45162.5554

result:

ok answer is 45162.5555000000

Test #29:

score: 0
Accepted
time: 251ms
memory: 1252kb

input:

2000 400
882856800 -8
866607093 -99
481381898 1
-488180557 55
-783185249 -2
-816111307 -174
99248396...

output:

2145.9655

result:

ok answer is 2145.9655000000

Test #30:

score: 0
Accepted
time: 241ms
memory: 1248kb

input:

2000 200
882856800 -1
866607093 -10
481381898 406927
-488180557 1
-783185249 -1483
-816111307 -8
992...

output:

3.4149

result:

ok answer is 3.4149000000

Test #31:

score: 0
Accepted
time: 224ms
memory: 1192kb

input:

2000 975
784172079 808971860
81381899 71917076
-712636352 -738530531
-622770179 -58502471
119667134 ...

output:

Forever

result:

ok OK, forever!

Subtask #6:

score: 0
Time Limit Exceeded

Test #32:

score: 0
Time Limit Exceeded

input:

99991 66666
-678240367 702595369
-125056128 663054848
574742591 -405224
-82244469 -11697083
55763190...

output:


result: