ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#174435 | #8. 小w、小j和小z | ZzhAllen | 100 | 4451ms | 3556kb | C++11 | 1.1kb | 2023-07-22 10:14:05 | 2023-07-22 10:14:06 |
answer
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#define double long double
using namespace std;
const int N = 1e5 + 10;
const double eps = 1e-8;
struct people {
int p,v;
} f[N];
double g[N];
int n,k;
bool cmp(people A,people B)
{
return A.p < B.p;
}
bool check(double mid){
int tmp = 0;
for (int i = 1; i <= n; i ++ )
{
double t = f[i].p + f[i].v * mid;
int k = lower_bound(g,g + tmp + 1,t - eps) - g;
if(k > tmp || fabs(g[k]-t) > eps){
g[k] = t;
if(k > tmp)tmp++;
}
}
return tmp + k >= n;
}
int main()
{
cin >> n >> k;
for (int i = 1; i <= n; i ++ )
cin >> f[i].p >> f[i].v;
sort(f + 1,f + 1 + n, cmp);
g[0] = -1e30;
double l = 0,r = 2e9,mid;
while(r - l > eps) {
mid = (l + r)/2.0;
if(check(mid)) l = mid;
else r = mid;
}
if(fabs(r-2e9)<eps) return puts("Forever"),0;
cout << fixed << setprecision(5) <<l<< endl;
}
Details
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1ms
memory: 1284kb
input:
20 10 -715624307 -28629151 957936621 17210368 -753657459 59049 -40974960 5153632 -402454312 -3450252...
output:
11.39993
result:
ok answer is 11.3999000000
Test #2:
score: 0
Accepted
time: 0ms
memory: 1288kb
input:
20 7 -715624307 -310 957936621 3 -753657459 1 -40974960 5 -402454312 -7424 874144191 -4 -227392025 7...
output:
5850568.50000
result:
ok answer is 5850568.5000000000
Test #3:
score: 0
Accepted
time: 0ms
memory: 1288kb
input:
20 4 -715624307 -1 957936621 3 -753657459 6 -40974960 1 -402454312 -1 874144191 -2 -227392025 9 -808...
output:
3926260.00000
result:
ok answer is 3926260.0000000000
Test #4:
score: 0
Accepted
time: 0ms
memory: 1284kb
input:
20 6 -715624307 -1 957936621 3 -753657459 1 -40974960 1 -402454312 -119 874144191 -1 -227392025 359 ...
output:
9635550.83333
result:
ok answer is 9635550.8333000001
Test #5:
score: 0
Accepted
time: 0ms
memory: 1180kb
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: 1292kb
input:
200 10 -487405787 3200000 725249085 28629151 -671026855 -4084101 38046635 45435424 -188495128 643634...
output:
0.00393
result:
ok answer is 0.0039000000
Test #7:
score: 0
Accepted
time: 0ms
memory: 1288kb
input:
200 10 -487405787 1 725249085 65536 -671026855 -100000000 38046635 1679616 -188495128 6561 -73172885...
output:
0.00419
result:
ok answer is 0.0041000000
Test #8:
score: 0
Accepted
time: 1ms
memory: 1288kb
input:
200 10 -487405787 3 725249085 2 -671026855 -6 38046635 5 -188495128 14 -731728859 12 -331220744 2 31...
output:
14398.51887
result:
ok answer is 14398.5188000000
Test #9:
score: 0
Accepted
time: 0ms
memory: 1288kb
input:
200 10 -487405787 56 725249085 2 -671026855 -8 38046635 1 -188495128 252 -731728859 28 -331220744 2 ...
output:
8320.36842
result:
ok answer is 8320.3684000000
Test #10:
score: 0
Accepted
time: 0ms
memory: 1292kb
input:
200 10 -487405787 11 725249085 8 -671026855 -1 38046635 1 -188495128 125 -731728859 106 -331220744 4...
output:
543.51868
result:
ok answer is 543.5186000000
Test #11:
score: 0
Accepted
time: 0ms
memory: 1188kb
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: 1288kb
input:
200 50 -487405787 3200000 725249085 28629151 -671026855 -4084101 38046635 45435424 -188495128 643634...
output:
0.03592
result:
ok answer is 0.0359000000
Test #13:
score: 0
Accepted
time: 0ms
memory: 1292kb
input:
200 100 -487405787 690807104 725249085 2685619 -671026855 -18399744 38046635 862801408 -188495128 54...
output:
0.12875
result:
ok answer is 0.1288000000
Test #14:
score: 0
Accepted
time: 0ms
memory: 1288kb
input:
200 90 -487405787 3 725249085 2 -671026855 -6 38046635 5 -188495128 14 -731728859 12 -331220744 2 31...
output:
3184277.23077
result:
ok answer is 3184277.2307000002
Test #15:
score: 0
Accepted
time: 0ms
memory: 1288kb
input:
200 60 -487405787 56 725249085 2 -671026855 -8 38046635 1 -188495128 252 -731728859 28 -331220744 2 ...
output:
572916.76190
result:
ok answer is 572916.7619000000
Test #16:
score: 0
Accepted
time: 0ms
memory: 1288kb
input:
200 30 -487405787 11 725249085 8 -671026855 -1 38046635 1 -188495128 125 -731728859 106 -331220744 4...
output:
7362.45059
result:
ok answer is 7362.4506000000
Test #17:
score: 0
Accepted
time: 0ms
memory: 1184kb
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: 7ms
memory: 1332kb
input:
2000 10 882856800 -387420489 866607093 -134217728 481381898 1 -488180557 1953125 -783185249 -19683 -...
output:
0.00017
result:
ok answer is 0.0001000000
Test #19:
score: 0
Accepted
time: 5ms
memory: 1328kb
input:
2000 10 882856800 -177147 866607093 -48828125 481381898 1 -488180557 48828125 -783185249 -362797056 ...
output:
0.00011
result:
ok answer is 0.0001000000
Test #20:
score: 0
Accepted
time: 3ms
memory: 1324kb
input:
2000 10 882856800 -1 866607093 -396 481381898 21 -488180557 6 -783185249 -10 -816111307 -33761 99248...
output:
2.62367
result:
ok answer is 2.6237000000
Test #21:
score: 0
Accepted
time: 6ms
memory: 1332kb
input:
2000 10 882856800 -3 866607093 -2 481381898 12 -488180557 8639109 -783185249 -12 -816111307 -96 9924...
output:
0.00083
result:
ok answer is 0.0008000000
Test #22:
score: 0
Accepted
time: 3ms
memory: 1332kb
input:
2000 10 882856800 -1 866607093 -10 481381898 406927 -488180557 1 -783185249 -1483 -816111307 -8 9924...
output:
0.00028
result:
ok answer is 0.0003000000
Test #23:
score: 0
Accepted
time: 6ms
memory: 1228kb
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: 5ms
memory: 1328kb
input:
2000 200 882856800 -177147 866607093 -48828125 481381898 1 -488180557 48828125 -783185249 -362797056...
output:
0.00244
result:
ok answer is 0.0024000000
Test #25:
score: 0
Accepted
time: 8ms
memory: 1324kb
input:
2000 500 882856800 -46656 866607093 -1000000 481381898 64000000 -488180557 481890304 -783185249 -466...
output:
0.00557
result:
ok answer is 0.0056000000
Test #26:
score: 0
Accepted
time: 5ms
memory: 1316kb
input:
2000 1200 882856800 -2000376 866607093 -344472101 481381898 97336 -488180557 278445077 -783185249 -1...
output:
0.03302
result:
ok answer is 0.0330000000
Test #27:
score: 0
Accepted
time: 7ms
memory: 1320kb
input:
2000 900 882856800 -1 866607093 -40 481381898 2 -488180557 2 -783185249 -1 -816111307 -70227 9924839...
output:
313683.66667
result:
ok answer is 313683.6667000000
Test #28:
score: 0
Accepted
time: 6ms
memory: 1320kb
input:
2000 600 882856800 -1 866607093 -396 481381898 21 -488180557 6 -783185249 -10 -816111307 -33761 9924...
output:
45162.55556
result:
ok answer is 45162.5555000000
Test #29:
score: 0
Accepted
time: 4ms
memory: 1328kb
input:
2000 400 882856800 -8 866607093 -99 481381898 1 -488180557 55 -783185249 -2 -816111307 -174 99248396...
output:
2145.96552
result:
ok answer is 2145.9655000000
Test #30:
score: 0
Accepted
time: 6ms
memory: 1328kb
input:
2000 200 882856800 -1 866607093 -10 481381898 406927 -488180557 1 -783185249 -1483 -816111307 -8 992...
output:
3.41493
result:
ok answer is 3.4149000000
Test #31:
score: 0
Accepted
time: 7ms
memory: 1212kb
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: 496ms
memory: 2632kb
input:
99991 66666 -678240367 702595369 -125056128 663054848 574742591 -405224 -82244469 -11697083 55763190...
output:
0.00127
result:
ok answer is 0.0013000000
Test #33:
score: 0
Accepted
time: 459ms
memory: 2920kb
input:
99992 45678 -505891895 4096 409303335 -387420489 800445369 -387420489 324934094 531441 -800995856 75...
output:
0.00093
result:
ok answer is 0.0009000000
Test #34:
score: 0
Accepted
time: 432ms
memory: 3196kb
input:
99993 32768 972961680 -512 -622461107 -512 -65245375 387420489 -652933487 40353607 919122483 -134217...
output:
0.00088
result:
ok answer is 0.0009000000
Test #35:
score: 0
Accepted
time: 422ms
memory: 3364kb
input:
99994 20102 -740844274 -2048 489732031 177147 964768051 1 -652641626 -48828125 -21363456 -48828125 8...
output:
0.00017
result:
ok answer is 0.0002000000
Test #36:
score: 0
Accepted
time: 386ms
memory: 3028kb
input:
99995 45454 -410995107 39 894702367 13 -426401694 -77 800430197 -1 -295413329 -9 708661134 -4 415710...
output:
6448.50000
result:
ok answer is 6448.5000000000
Test #37:
score: 0
Accepted
time: 381ms
memory: 3152kb
input:
99996 35555 -14445778 13 -451475811 -3 444048318 -13004 422621424 -1 742439995 -2 723182696 -7 68727...
output:
1573.33333
result:
ok answer is 1573.3333000000
Test #38:
score: 0
Accepted
time: 386ms
memory: 3292kb
input:
99997 25600 -730866353 10 -218920426 -2 64717974 -1 137126596 -5 46821900 10155 745056512 17285 -964...
output:
119.08122
result:
ok answer is 119.0812000000
Test #39:
score: 0
Accepted
time: 524ms
memory: 3412kb
input:
99998 15263 -467407842 -1 -422165068 -2 915790698 -332 354357273 2 387305689 1714 -445403298 704 -83...
output:
1.48883
result:
ok answer is 1.4888000000
Test #40:
score: 0
Accepted
time: 371ms
memory: 3556kb
input:
99999 4999 -845589366 -183 771287727 -36 409548298 7543 -261071768 52 -182275548 3385 -137396908 121...
output:
0.00098
result:
ok answer is 0.0010000000
Test #41:
score: 0
Accepted
time: 514ms
memory: 2924kb
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