ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#159021 | #8. 小w、小j和小z | wuzr | 100 | 3919ms | 6704kb | C++ | 1.3kb | 2022-08-28 18:58:22 | 2022-08-28 18:58:24 |
answer
#include<bits/stdc++.h>
using namespace std;
#define re register
#define rep(i,a,b) for(ll i(a);i<=b;++i)
#define per(i,a,b) for(ll i(a);i>=b;--i)
#define ll long long
#define swap(x,y) x^=y^=x^=y
#define y1 yyy1
#define int ll
#define double long double
struct node {
int p, v;
} a[100005];
int n, k;
int dp[100005];
double pos[100005], low[100005];
bool ck(double x) {
rep(i, 1, n) pos[i] = a[i].p + a[i].v * x;
memset(dp, 0, sizeof dp);
int mx = 0;
low[0] = -9e18;
rep(i, 1, n) {
dp[i] = upper_bound(low, low + mx + 1, pos[i] - 1e-7) - low;
if (dp[i] > mx) {
mx = dp[i];
low[mx] = pos[i];
} else low[dp[i]] = min(low[dp[i]], pos[i]);
}
return mx + k >= n;
}
bool cmp(node x, node y) {
if (x.p == y.p) return x.v > y.v;
else return x.p < y.p;
}
signed main() {
ios::sync_with_stdio(0);
cin >> n >> k;
rep(i, 1, n) cin >> a[i].p >> a[i].v;
sort(a + 1, a + n + 1, cmp);
int t = 1;
rep(i, 2, n) {
if (a[i].p == a[t].p && a[i].v == a[t].v) k--;
else a[++t] = a[i];
}
n = t;
double l = 0, r = 2.5e9;
while (l + 1e-7 < r) {
double mid = (l + r) / 2;
if (ck(mid)) l = mid;
else r = mid;
}
double ans = (l + r) / 2;
if (ans > 2.4e9) puts("Forever");
else printf("%.6Lf", ans);
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 3ms
memory: 2088kb
input:
20 10 -715624307 -28629151 957936621 17210368 -753657459 59049 -40974960 5153632 -402454312 -3450252...
output:
11.399931
result:
ok answer is 11.3999000000
Test #2:
score: 0
Accepted
time: 3ms
memory: 2088kb
input:
20 7 -715624307 -310 957936621 3 -753657459 1 -40974960 5 -402454312 -7424 874144191 -4 -227392025 7...
output:
5850568.500000
result:
ok answer is 5850568.5000000000
Test #3:
score: 0
Accepted
time: 3ms
memory: 2088kb
input:
20 4 -715624307 -1 957936621 3 -753657459 6 -40974960 1 -402454312 -1 874144191 -2 -227392025 9 -808...
output:
3926260.000000
result:
ok answer is 3926260.0000000000
Test #4:
score: 0
Accepted
time: 0ms
memory: 2088kb
input:
20 6 -715624307 -1 957936621 3 -753657459 1 -40974960 1 -402454312 -119 874144191 -1 -227392025 359 ...
output:
9635550.833333
result:
ok answer is 9635550.8333000001
Test #5:
score: 0
Accepted
time: 3ms
memory: 2032kb
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: 2ms
memory: 2092kb
input:
200 10 -487405787 3200000 725249085 28629151 -671026855 -4084101 38046635 45435424 -188495128 643634...
output:
0.003931
result:
ok answer is 0.0039000000
Test #7:
score: 0
Accepted
time: 1ms
memory: 2092kb
input:
200 10 -487405787 1 725249085 65536 -671026855 -100000000 38046635 1679616 -188495128 6561 -73172885...
output:
0.004186
result:
ok answer is 0.0041000000
Test #8:
score: 0
Accepted
time: 1ms
memory: 2096kb
input:
200 10 -487405787 3 725249085 2 -671026855 -6 38046635 5 -188495128 14 -731728859 12 -331220744 2 31...
output:
14398.518868
result:
ok answer is 14398.5188000000
Test #9:
score: 0
Accepted
time: 2ms
memory: 2096kb
input:
200 10 -487405787 56 725249085 2 -671026855 -8 38046635 1 -188495128 252 -731728859 28 -331220744 2 ...
output:
8320.368421
result:
ok answer is 8320.3684000000
Test #10:
score: 0
Accepted
time: 3ms
memory: 2096kb
input:
200 10 -487405787 11 725249085 8 -671026855 -1 38046635 1 -188495128 125 -731728859 106 -331220744 4...
output:
543.518678
result:
ok answer is 543.5186000000
Test #11:
score: 0
Accepted
time: 0ms
memory: 2040kb
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: 3ms
memory: 2092kb
input:
200 50 -487405787 3200000 725249085 28629151 -671026855 -4084101 38046635 45435424 -188495128 643634...
output:
0.035919
result:
ok answer is 0.0359000000
Test #13:
score: 0
Accepted
time: 0ms
memory: 2096kb
input:
200 100 -487405787 690807104 725249085 2685619 -671026855 -18399744 38046635 862801408 -188495128 54...
output:
0.128752
result:
ok answer is 0.1288000000
Test #14:
score: 0
Accepted
time: 4ms
memory: 2096kb
input:
200 90 -487405787 3 725249085 2 -671026855 -6 38046635 5 -188495128 14 -731728859 12 -331220744 2 31...
output:
3184277.230769
result:
ok answer is 3184277.2307000002
Test #15:
score: 0
Accepted
time: 2ms
memory: 2096kb
input:
200 60 -487405787 56 725249085 2 -671026855 -8 38046635 1 -188495128 252 -731728859 28 -331220744 2 ...
output:
572916.761905
result:
ok answer is 572916.7619000000
Test #16:
score: 0
Accepted
time: 2ms
memory: 2100kb
input:
200 30 -487405787 11 725249085 8 -671026855 -1 38046635 1 -188495128 125 -731728859 106 -331220744 4...
output:
7362.450593
result:
ok answer is 7362.4506000000
Test #17:
score: 0
Accepted
time: 5ms
memory: 2044kb
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: 12ms
memory: 2184kb
input:
2000 10 882856800 -387420489 866607093 -134217728 481381898 1 -488180557 1953125 -783185249 -19683 -...
output:
0.000167
result:
ok answer is 0.0001000000
Test #19:
score: 0
Accepted
time: 8ms
memory: 2180kb
input:
2000 10 882856800 -177147 866607093 -48828125 481381898 1 -488180557 48828125 -783185249 -362797056 ...
output:
0.000114
result:
ok answer is 0.0001000000
Test #20:
score: 0
Accepted
time: 11ms
memory: 2176kb
input:
2000 10 882856800 -1 866607093 -396 481381898 21 -488180557 6 -783185249 -10 -816111307 -33761 99248...
output:
2.623671
result:
ok answer is 2.6237000000
Test #21:
score: 0
Accepted
time: 11ms
memory: 2180kb
input:
2000 10 882856800 -3 866607093 -2 481381898 12 -488180557 8639109 -783185249 -12 -816111307 -96 9924...
output:
0.000829
result:
ok answer is 0.0008000000
Test #22:
score: 0
Accepted
time: 11ms
memory: 2184kb
input:
2000 10 882856800 -1 866607093 -10 481381898 406927 -488180557 1 -783185249 -1483 -816111307 -8 9924...
output:
0.000284
result:
ok answer is 0.0003000000
Test #23:
score: 0
Accepted
time: 10ms
memory: 2124kb
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: 12ms
memory: 2180kb
input:
2000 200 882856800 -177147 866607093 -48828125 481381898 1 -488180557 48828125 -783185249 -362797056...
output:
0.002440
result:
ok answer is 0.0024000000
Test #25:
score: 0
Accepted
time: 12ms
memory: 2176kb
input:
2000 500 882856800 -46656 866607093 -1000000 481381898 64000000 -488180557 481890304 -783185249 -466...
output:
0.005573
result:
ok answer is 0.0056000000
Test #26:
score: 0
Accepted
time: 13ms
memory: 2164kb
input:
2000 1200 882856800 -2000376 866607093 -344472101 481381898 97336 -488180557 278445077 -783185249 -1...
output:
0.033021
result:
ok answer is 0.0330000000
Test #27:
score: 0
Accepted
time: 12ms
memory: 2172kb
input:
2000 900 882856800 -1 866607093 -40 481381898 2 -488180557 2 -783185249 -1 -816111307 -70227 9924839...
output:
313683.666667
result:
ok answer is 313683.6667000000
Test #28:
score: 0
Accepted
time: 8ms
memory: 2176kb
input:
2000 600 882856800 -1 866607093 -396 481381898 21 -488180557 6 -783185249 -10 -816111307 -33761 9924...
output:
45162.555556
result:
ok answer is 45162.5555000000
Test #29:
score: 0
Accepted
time: 8ms
memory: 2180kb
input:
2000 400 882856800 -8 866607093 -99 481381898 1 -488180557 55 -783185249 -2 -816111307 -174 99248396...
output:
2145.965517
result:
ok answer is 2145.9655000000
Test #30:
score: 0
Accepted
time: 8ms
memory: 2180kb
input:
2000 200 882856800 -1 866607093 -10 481381898 406927 -488180557 1 -783185249 -1483 -816111307 -8 992...
output:
3.414934
result:
ok answer is 3.4149000000
Test #31:
score: 0
Accepted
time: 5ms
memory: 2116kb
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: 415ms
memory: 5748kb
input:
99991 66666 -678240367 702595369 -125056128 663054848 574742591 -405224 -82244469 -11697083 55763190...
output:
0.001274
result:
ok answer is 0.0013000000
Test #33:
score: 0
Accepted
time: 389ms
memory: 6128kb
input:
99992 45678 -505891895 4096 409303335 -387420489 800445369 -387420489 324934094 531441 -800995856 75...
output:
0.000926
result:
ok answer is 0.0009000000
Test #34:
score: 0
Accepted
time: 513ms
memory: 6312kb
input:
99993 32768 972961680 -512 -622461107 -512 -65245375 387420489 -652933487 40353607 919122483 -134217...
output:
0.000882
result:
ok answer is 0.0009000000
Test #35:
score: 0
Accepted
time: 348ms
memory: 6480kb
input:
99994 20102 -740844274 -2048 489732031 177147 964768051 1 -652641626 -48828125 -21363456 -48828125 8...
output:
0.000171
result:
ok answer is 0.0002000000
Test #36:
score: 0
Accepted
time: 327ms
memory: 6132kb
input:
99995 45454 -410995107 39 894702367 13 -426401694 -77 800430197 -1 -295413329 -9 708661134 -4 415710...
output:
6448.500000
result:
ok answer is 6448.5000000000
Test #37:
score: 0
Accepted
time: 342ms
memory: 6264kb
input:
99996 35555 -14445778 13 -451475811 -3 444048318 -13004 422621424 -1 742439995 -2 723182696 -7 68727...
output:
1573.333333
result:
ok answer is 1573.3333000000
Test #38:
score: 0
Accepted
time: 332ms
memory: 6424kb
input:
99997 25600 -730866353 10 -218920426 -2 64717974 -1 137126596 -5 46821900 10155 745056512 17285 -964...
output:
119.081218
result:
ok answer is 119.0812000000
Test #39:
score: 0
Accepted
time: 318ms
memory: 6544kb
input:
99998 15263 -467407842 -1 -422165068 -2 915790698 -332 354357273 2 387305689 1714 -445403298 704 -83...
output:
1.488829
result:
ok answer is 1.4888000000
Test #40:
score: 0
Accepted
time: 315ms
memory: 6704kb
input:
99999 4999 -845589366 -183 771287727 -36 409548298 7543 -261071768 52 -182275548 3385 -137396908 121...
output:
0.000984
result:
ok answer is 0.0010000000
Test #41:
score: 0
Accepted
time: 442ms
memory: 6116kb
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