ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#143354 | #8. 小w、小j和小z | Xiao_mo | 100 | 1919ms | 3512kb | C++ | 1.3kb | 2021-11-18 06:57:36 | 2021-11-18 06:57:38 |
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;
double x;
}a[N];
double b[N];
inline bool cmp(data a,data b){
return a.p<b.p;
}
inline bool check(double x){
for(int i=1;i<=n;i++)a[i].x=a[i].p+x*a[i].v;
int cnt=0;
for(int i=1;i<=n;i++){
if(!cnt||b[cnt]<a[i].x)b[++cnt]=a[i].x;
if(cnt&&fabs(b[cnt]-a[i].x)<0.00001)continue;
int t=upper_bound(b+1,b+1+cnt,a[i].x)-b;
b[t]=a[i].x;
}
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();
sort(a+1,a+1+n,cmp);
double l=0,r=2e9,ans;
while(r-l>=0.00001){
double mid=(l+r)/2;
if(check(mid))ans=l=mid;
else r=mid;
}
if(ans>=2e9-0.0001)printf("Forever");
else printf("%.4lf",l);
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 1212kb
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: 1216kb
input:
20 7 -715624307 -310 957936621 3 -753657459 1 -40974960 5 -402454312 -7424 874144191 -4 -227392025 7...
output:
5850568.5000
result:
ok answer is 5850568.5000000000
Test #3:
score: 0
Accepted
time: 0ms
memory: 1212kb
input:
20 4 -715624307 -1 957936621 3 -753657459 6 -40974960 1 -402454312 -1 874144191 -2 -227392025 9 -808...
output:
3926260.0000
result:
ok answer is 3926260.0000000000
Test #4:
score: 0
Accepted
time: 0ms
memory: 1212kb
input:
20 6 -715624307 -1 957936621 3 -753657459 1 -40974960 1 -402454312 -119 874144191 -1 -227392025 359 ...
output:
9635550.8333
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: 1212kb
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: 0ms
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: 0ms
memory: 1216kb
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: 0ms
memory: 1220kb
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: 1216kb
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: 0ms
memory: 1220kb
input:
200 90 -487405787 3 725249085 2 -671026855 -6 38046635 5 -188495128 14 -731728859 12 -331220744 2 31...
output:
3184277.2308
result:
ok answer is 3184277.2307000002
Test #15:
score: 0
Accepted
time: 0ms
memory: 1220kb
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: 1ms
memory: 1216kb
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: 0ms
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: 3ms
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: 4ms
memory: 1256kb
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: 0ms
memory: 1252kb
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: 2ms
memory: 1252kb
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: 3ms
memory: 1256kb
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: 1ms
memory: 1200kb
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: 3ms
memory: 1256kb
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: 4ms
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: 2ms
memory: 1244kb
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: 3ms
memory: 1256kb
input:
2000 900 882856800 -1 866607093 -40 481381898 2 -488180557 2 -783185249 -1 -816111307 -70227 9924839...
output:
313683.6667
result:
ok answer is 313683.6667000000
Test #28:
score: 0
Accepted
time: 0ms
memory: 1256kb
input:
2000 600 882856800 -1 866607093 -396 481381898 21 -488180557 6 -783185249 -10 -816111307 -33761 9924...
output:
45162.5556
result:
ok answer is 45162.5555000000
Test #29:
score: 0
Accepted
time: 0ms
memory: 1256kb
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: 0ms
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: 0ms
memory: 1196kb
input:
2000 975 784172079 808971860 81381899 71917076 -712636352 -738530531 -622770179 -58502471 119667134 ...
output:
Forever
result:
ok OK, forever!
Subtask #6:
score: 20
Accepted
Test #32:
score: 20
Accepted
time: 263ms
memory: 3052kb
input:
99991 66666 -678240367 702595369 -125056128 663054848 574742591 -405224 -82244469 -11697083 55763190...
output:
0.0013
result:
ok answer is 0.0013000000
Test #33:
score: 0
Accepted
time: 218ms
memory: 3192kb
input:
99992 45678 -505891895 4096 409303335 -387420489 800445369 -387420489 324934094 531441 -800995856 75...
output:
0.0009
result:
ok answer is 0.0009000000
Test #34:
score: 0
Accepted
time: 219ms
memory: 3328kb
input:
99993 32768 972961680 -512 -622461107 -512 -65245375 387420489 -652933487 40353607 919122483 -134217...
output:
0.0009
result:
ok answer is 0.0009000000
Test #35:
score: 0
Accepted
time: 196ms
memory: 3416kb
input:
99994 20102 -740844274 -2048 489732031 177147 964768051 1 -652641626 -48828125 -21363456 -48828125 8...
output:
0.0002
result:
ok answer is 0.0002000000
Test #36:
score: 0
Accepted
time: 178ms
memory: 3248kb
input:
99995 45454 -410995107 39 894702367 13 -426401694 -77 800430197 -1 -295413329 -9 708661134 -4 415710...
output:
6448.5000
result:
ok answer is 6448.5000000000
Test #37:
score: 0
Accepted
time: 159ms
memory: 3316kb
input:
99996 35555 -14445778 13 -451475811 -3 444048318 -13004 422621424 -1 742439995 -2 723182696 -7 68727...
output:
1573.3333
result:
ok answer is 1573.3333000000
Test #38:
score: 0
Accepted
time: 165ms
memory: 3384kb
input:
99997 25600 -730866353 10 -218920426 -2 64717974 -1 137126596 -5 46821900 10155 745056512 17285 -964...
output:
119.0812
result:
ok answer is 119.0812000000
Test #39:
score: 0
Accepted
time: 147ms
memory: 3440kb
input:
99998 15263 -467407842 -1 -422165068 -2 915790698 -332 354357273 2 387305689 1714 -445403298 704 -83...
output:
1.4888
result:
ok answer is 1.4888000000
Test #40:
score: 0
Accepted
time: 140ms
memory: 3512kb
input:
99999 4999 -845589366 -183 771287727 -36 409548298 7543 -261071768 52 -182275548 3385 -137396908 121...
output:
0.0010
result:
ok answer is 0.0010000000
Test #41:
score: 0
Accepted
time: 208ms
memory: 3200kb
input:
100000 48364 979472386 980717496 207916820 208951865 -236221008 -237374910 348596303 348678721 70817...
output:
Forever
result:
ok OK, forever!
Extra Test:
score: 0
Extra Test Passed