QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#116294 | #4144. 基站建设 | SnowNorth | 100 ✓ | 2750ms | 286984kb | C++14 | 1.5kb | 2023-06-28 13:33:51 | 2023-06-28 13:33:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 10;
double x[N], rd[N], v[N], f[N], X[N], Y[N];
int q[N], tail;
int id[N], tmp[N];
double slope (int i, int j) { return (Y[i] - Y[j]) / (X[i] - X[j]); }
void dvd (int l, int r) {
if (l == r) {
Y[l] = f[l] - x[l] * sqrt(rd[l]) / (rd[l] * 2);
return ;
}
int mid = (l + r) >> 1;
dvd (l, mid);
tail = 0;
for (int i = l; i <= mid; i++) {
while (tail > 1 && slope(q[tail], q[tail - 1]) >= slope(id[i], q[tail])) tail--;
q[++tail] = id[i];
}
for (int i = mid + 1; i <= r; i++) {
while (tail > 1 && slope(q[tail], q[tail - 1]) >= -x[i] / 2) tail--;
int j = q[tail];
f[i] = min(f[i], f[j] + v[i] + (x[i] - x[j]) / (sqrt(rd[j]) * 2));
}
dvd (mid + 1, r);
int p1 = l, p2 = mid + 1, pk = l;
while (p1 <= mid || p2 <= r) {
if (p2 > r || (p1 <= mid && X[id[p1]] <= X[id[p2]])) tmp[pk++] = id[p1++];
else tmp[pk++] = id[p2++];
}
for (int i = l; i <= r; i++) id[i] = tmp[i];
}
void solve() {
int n;
double m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> x[i] >> rd[i] >> v[i];
if (rd[i] == 0) { --i; --n; continue ; }
id[i] = i;
X[i] = sqrt(rd[i]) / rd[i];
}
for (int i = 0; i <= n; i++) f[i] = 1e16;
f[1] = v[1];
dvd (1, n);
double ans = 1e16;
for (int i = 1; i <= n; i++) {
if (x[i] + rd[i] >= m) ans = min(ans, f[i]);
}
printf("%.3lf", ans);
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 1ms
memory: 20004kb
input:
1000 248898 379 966 5573 674 779 358 924 376 2936 1066 958 9121 1502 254 2106 1629 3 8415 1630 368 5333 1672 508 6388 1729 527 2753 2153 174 5500 2375 791 1290 2529 595 4016 2617 456 1691 2784 801 5672 3105 223 327 3172 337 102 3405 708 3634 3689 356 2453 4031 896 2949 4246 535 4778 4375 816 7037 44...
output:
11561.763
result:
ok single line: '11561.763'
Test #2:
score: 10
Accepted
time: 4ms
memory: 20120kb
input:
2000 1009425 860 952 5247 1771 1243 5679 1902 1082 3972 2285 1121 5994 2993 1253 2007 3863 1026 1921 4401 485 3646 5316 158 7864 6025 1443 2662 6066 1388 4151 6967 410 6641 7454 1242 3805 8204 1185 431 8603 1374 7611 8988 526 8129 9273 675 5837 9468 781 82 9916 306 7413 10444 250 9539 10775 270 5302...
output:
22583.431
result:
ok single line: '22583.431'
Test #3:
score: 10
Accepted
time: 14ms
memory: 24428kb
input:
30000 208261115 864 28571 1834 15485 12408 212 16594 9183 1748 25702 15920 4424 30991 6177 1810 35347 10436 5689 43947 27170 866 52883 5892 4169 63085 26807 5854 64703 9156 879 68956 13588 7353 77942 27113 7064 82404 24411 54 93858 204 6374 108740 24357 5258 117968 13553 943 120815 29010 1804 130438...
output:
606301.371
result:
ok single line: '606301.371'
Test #4:
score: 10
Accepted
time: 26ms
memory: 20188kb
input:
50000 521464011 9465 11023 8923 15123 14734 393 31578 38109 1936 38818 38492 3283 54952 7494 23 57653 35312 497 71831 48863 4431 72658 6086 3397 95627 45573 534 113000 14537 2071 123604 33183 5365 144848 3484 3886 158422 47748 3607 160664 47145 5806 164928 30546 2181 172661 22370 1669 184155 9687 56...
output:
1184951.390
result:
ok single line: '1184951.390'
Test #5:
score: 10
Accepted
time: 60ms
memory: 28612kb
input:
100000 1639535370 12980 73364 1188 43346 95781 8259 64974 26132 9360 86097 99075 1456 91274 66356 3257 112682 80107 5853 120878 89048 8102 125615 92357 1693 129130 92547 4325 151382 99569 597 180542 80444 2690 182515 34201 5375 211889 54344 3238 230903 86907 1980 255466 99177 4459 277879 92999 5910 ...
output:
2597807.323
result:
ok single line: '2597807.323'
Test #6:
score: 10
Accepted
time: 56ms
memory: 22528kb
input:
100000 1637586710 8498 43078 592 37847 3343 6937 50426 95305 3666 72079 2174 3863 82110 43091 9302 93248 12219 2048 114072 93664 2800 118639 90789 4199 125559 76868 1854 141262 58071 1715 142014 98674 421 156871 89953 8904 162190 53121 3784 194286 83640 3232 206136 1300 5037 213268 76646 2780 233979...
output:
2592671.384
result:
ok single line: '2592671.384'
Test #7:
score: 10
Accepted
time: 2273ms
memory: 286984kb
input:
5000000 12499985000004 2499997 1 5672 4999994 2 5672 7499991 3 5672 9999988 4 5672 12499985 5 5672 14999982 6 5672 17499979 7 5672 19999976 8 5672 22499973 9 5672 24999970 10 5672 27499967 11 5672 29999964 12 5672 32499961 13 5672 34999958 14 5672 37499955 15 5672 39999952 16 5672 42499949 17 5672 4...
output:
5603546606.710
result:
ok single line: '5603546606.710'
Test #8:
score: 10
Accepted
time: 2217ms
memory: 284796kb
input:
5000000 12499985000003 2499997 5000000 5672 4999994 1 5672 7499991 2 5672 9999988 3 5672 12499985 4 5672 14999982 5 5672 17499979 6 5672 19999976 7 5672 22499973 8 5672 24999970 9 5672 27499967 10 5672 29999964 11 5672 32499961 12 5672 34999958 13 5672 37499955 14 5672 39999952 15 5672 42499949 16 5...
output:
2795091284.724
result:
ok single line: '2795091284.724'
Test #9:
score: 10
Accepted
time: 2551ms
memory: 278076kb
input:
5000000 12499985000003 2499997 5 4321 4999994 4 4321 7499991 1 4321 9999988 2 4321 12499985 3 4321 14999982 10 4321 17499979 9 4321 19999976 8 4321 22499973 7 4321 24999970 6 4321 27499967 15 4321 29999964 14 4321 32499961 11 4321 34999958 12 4321 37499955 13 4321 39999952 16 4321 42499949 17 4321 4...
output:
5599079762.649
result:
ok single line: '5599079762.649'
Test #10:
score: 10
Accepted
time: 2750ms
memory: 277420kb
input:
5000000 12499985000004 2499997 5 4321 4999994 1 4322 7499991 4 4322 9999988 3 4321 12499985 2 4322 14999982 6 4321 17499979 7 4322 19999976 8 4322 22499973 10 4322 24999970 9 4321 27499967 11 4323 29999964 12 4323 32499961 13 4322 34999958 15 4323 37499955 14 4322 39999952 20 4323 42499949 18 4321 4...
output:
5599372679.325
result:
ok single line: '5599372679.325'