ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#152038 | #8. 小w、小j和小z | LightningUZ | 80 | 3523ms | 1256kb | C++11 | 1.7kb | 2022-07-30 18:37:54 | 2022-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...