ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#152028 | #8. 小w、小j和小z | LightningUZ | 80 | 3424ms | 1248kb | C++11 | 1.3kb | 2022-07-30 18:30:55 | 2022-07-30 18:30:56 |
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;
}
int f[N];
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){f[i]=1; for(int j=1;j<i;++j)if(a[j].x<=a[i].x-0.001)f[i]=max(f[i],f[j]+1);}
for(int i=1;i<=n;++i)cnt=max(cnt,f[i]);
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: 1212kb
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: 1212kb
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: 1212kb
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: 3ms
memory: 1208kb
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: 1208kb
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: 3ms
memory: 1212kb
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: 3ms
memory: 1212kb
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: 3ms
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: 1212kb
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: 1208kb
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: 1216kb
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: 0ms
memory: 1212kb
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: 1212kb
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: 254ms
memory: 1240kb
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: 245ms
memory: 1244kb
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: 241ms
memory: 1236kb
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: 233ms
memory: 1240kb
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: 235ms
memory: 1240kb
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: 239ms
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: 244ms
memory: 1244kb
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: 263ms
memory: 1244kb
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: 278ms
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: 240ms
memory: 1244kb
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: 243ms
memory: 1248kb
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: 236ms
memory: 1248kb
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: 236ms
memory: 1236kb
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: 218ms
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...