QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#136297 | #2417. Height Profile | BUET_TEAM_ONE | AC ✓ | 1493ms | 11236kb | C++23 | 2.4kb | 2023-08-07 19:30:49 | 2023-08-07 19:30:50 |
Judging History
answer
#include <bits/stdc++.h>
typedef long long int ll;
#define endl '\n'
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>
#define fill(x, y) memset(x, y, sizeof(x))
#define all(x) (x).begin(), (x).end()
#define debug(x) { cerr << #x << " = " << x << endl; }
#define IO { ios_base::sync_with_stdio(false); cin.tie(0); }
#define read(x) freopen(x, "r", stdin)
#define write(x) freopen(x, "w", stdout)
using namespace std;
typedef vector<int> vi;
double getAns(vector<ll> h, ll n, ll k, long double g) {
ll m = g;
vector<ll> c(n + 100);
vector<pair<ll, ll>> arr, arr2;
for (int i=0; i<n; i++) {
c[i] = h[i] - m * i;
arr.push_back({c[i], i});
arr2.push_back({c[i], -i});
}
sort(all(arr));
sort(all(arr2));
ll max_i = 0;
ll min_i = n;
vector<ll> mx_nxt(n + 100, -1);
for (int i= n - 1; i>=0; i--) {
if (max_i > arr[i].second) mx_nxt[arr[i].second] = max_i;
max_i = max(max_i, arr[i].second);
}
double ans = 0;
for (int i=0; i<n; i++) {
if (mx_nxt[i] != -1) {
if (mx_nxt[i] == n-1) ans = max(ans, (double) (n - 1 - i) );
else {
double x2 = mx_nxt[i];
double y2 = h[x2];
double x3 = x2+1;
double y3 = h[x3];
double x = y2 - c[i] - (y3 - y2) * x2;
if (m - y3 + y2 == 0) continue;
x /= (double) (m - y3 + y2);
ans = max(ans, x - (double)i);
}
}
}
return ans;
}
void solve() {
ll n, k;
cin >> n >> k;
n++;
vector<ll> h(n);
for (int i=0; i<n; i++) {
cin >> h[i];
}
while(k--) {
long double g;
cin >> g;
g *= 10.0;
double a1 = getAns(h, n, k, g);
reverse(all(h));
for (ll &x: h) x = -x;
double a2 = getAns(h, n, k, g);
for (ll &x: h) x = -x;
reverse(all(h));
double a = max(a1, a2);
if (a == 0) cout << "impossible" << endl;
else cout << a << endl;
}
}
int main() {
//IO;
cout << fixed << setprecision(10);
solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 535ms
memory: 7436kb
input:
49995 50 62462505 62457507 62452509 62447511 62442513 62437515 62432518 62427521 62422524 62417527 62412530 62407534 62402538 62397542 62392546 62387550 62382555 62377560 62372565 62367570 62362575 62357581 62352587 62347593 62342599 62337605 62332612 62327619 62322626 62317633 62312640 62307648 623...
output:
41475.0000000000 40035.0000000000 45605.0000000000 49995.0000000000 42145.0000000000 49995.0000000000 42455.0000000000 41115.0000000000 45285.0000000000 46515.0000000000 48045.0000000000 49995.0000000000 49995.0000000000 44155.0000000000 49995.0000000000 49995.0000000000 49995.0000000000 44615.00000...
result:
ok
Test #2:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
17 13 4041 3479 2756 2495 2230 1428 546 18 0 677 1337 1190 1590 2301 2721 2221 3151 3205 62.6 -43.2 47.9 83.1 -61.3 -40.3 -73.1 18.0 -58.5 23.4 -35.3 56.9 -43.1
output:
2.1319875776 17.0000000000 3.1501597444 1.1274131274 17.0000000000 17.0000000000 17.0000000000 11.6393596987 17.0000000000 11.0761648746 17.0000000000 2.3390119250 17.0000000000
result:
ok
Test #3:
score: 0
Accepted
time: 2ms
memory: 3776kb
input:
8 35 0 582 545 1150 1546 1873 2284 2508 1600 18.1 79.8 -62.3 90.7 63.6 -2.3 -57.5 15.3 -64.0 -6.2 3.8 62.1 -25.1 -67.3 31.3 -20.8 -63.2 16.5 94.3 -87.6 -96.1 -40.6 11.6 64.0 0.9 52.1 96.1 -14.0 25.4 -9.6 20.0 65.6 -24.6 -67.2 47.7
output:
8.0000000000 impossible 8.0000000000 impossible impossible 8.0000000000 8.0000000000 8.0000000000 8.0000000000 8.0000000000 8.0000000000 impossible 8.0000000000 8.0000000000 7.2596232596 8.0000000000 8.0000000000 8.0000000000 impossible 8.0000000000 8.0000000000 8.0000000000 8.0000000000 impossible ...
result:
ok
Test #4:
score: 0
Accepted
time: 4ms
memory: 3768kb
input:
714 50 1701 1466 1013 2008 1886 1822 2301 1428 1953 1955 2635 2817 1939 1352 622 125 965 1919 2122 2845 3563 4484 4102 3827 4632 5128 4478 4886 4607 3870 4745 4716 3945 3118 3098 2728 2808 3664 3633 3181 3221 3668 3561 3369 2475 2844 1876 2095 3022 2393 2453 3158 3586 3004 2176 1644 1409 1812 2173 2...
output:
280.5006765900 714.0000000000 48.0085287846 714.0000000000 714.0000000000 2.1694711538 5.3420245399 714.0000000000 714.0000000000 106.5514018692 5.7953410982 6.5050000000 2.0628571429 714.0000000000 143.2541254125 714.0000000000 714.0000000000 279.0269151139 2.1513706794 714.0000000000 714.000000000...
result:
ok
Test #5:
score: 0
Accepted
time: 2ms
memory: 3728kb
input:
985 11 10319 9512 9739 10112 9366 9830 9727 8749 9047 8710 8636 8768 8866 8533 8106 8627 8391 7721 8692 9407 9995 9158 9902 9698 9743 8827 9284 10073 10616 9894 10763 10667 10554 10186 9575 9576 8742 8375 7602 7519 6662 6753 6791 7417 7650 7268 7536 7578 7925 7953 7059 6380 5985 5685 6339 6560 5881 ...
output:
985.0000000000 985.0000000000 106.5610795455 985.0000000000 985.0000000000 1.0151515152 985.0000000000 985.0000000000 985.0000000000 66.7324380165 37.9305856833
result:
ok
Test #6:
score: 0
Accepted
time: 19ms
memory: 4040kb
input:
3455 44 12726 13370 13788 13292 12499 11838 11266 12053 11594 11314 12084 12102 11597 10689 10544 10468 10936 11236 10446 10827 10778 11685 11774 12557 12227 11436 11856 12090 11676 11925 11182 12057 12729 12515 12235 12824 12520 12097 11134 11487 11211 11628 12600 12621 12797 12391 11900 12036 1194...
output:
3455.0000000000 8.5344129555 18.0569105691 3455.0000000000 47.4932614555 17.7142857143 3455.0000000000 2000.5803480041 3455.0000000000 3455.0000000000 1.1875000000 3455.0000000000 1247.0912220310 555.2099533437 3455.0000000000 3455.0000000000 10.0599400599 3455.0000000000 553.9326424870 71.858291457...
result:
ok
Test #7:
score: 0
Accepted
time: 23ms
memory: 3932kb
input:
5000 48 16040 16489 16513 17506 16650 16551 17496 18381 19030 19813 19577 19082 18434 17836 17602 18337 17633 18386 18998 18926 19443 19180 18477 18346 19221 19029 19706 19141 18295 17627 16631 16063 16393 17194 17745 17133 16258 16569 16377 16444 17313 17651 17355 17540 17439 17224 17401 17167 1730...
output:
19.5068205666 5000.0000000000 8.2338403042 1.0728476821 5000.0000000000 8.3771760155 5000.0000000000 5000.0000000000 5000.0000000000 5000.0000000000 4.8493870403 5000.0000000000 634.9572127139 5000.0000000000 5000.0000000000 4.7091836735 5.2443572130 5000.0000000000 5000.0000000000 13.0585937500 500...
result:
ok
Test #8:
score: 0
Accepted
time: 7ms
memory: 3808kb
input:
1565 46 5256 4856 4469 5130 6111 6997 7511 8071 7550 6693 6600 6248 6288 5742 5733 6391 5653 6325 6546 7456 7949 7020 6346 6084 6212 6202 5947 5905 6387 5803 6478 7033 7856 7438 7831 7857 7835 8690 9274 10241 10663 10339 10069 9408 9064 9040 9759 9724 10015 10480 10227 10907 11713 11556 10830 10873 ...
output:
1565.0000000000 5.8062827225 1565.0000000000 28.0774962742 1565.0000000000 10.0372914622 3.3953488372 1565.0000000000 271.7148846960 1565.0000000000 271.1464435146 6.6682554814 11.0840543881 4.3120300752 1565.0000000000 7.0481400438 6.3533151680 1565.0000000000 6.5742481203 1565.0000000000 1565.0000...
result:
ok
Test #9:
score: 0
Accepted
time: 33ms
memory: 4264kb
input:
7291 50 25433 26269 27073 27188 26451 26116 26029 26321 25965 26248 26212 26412 26027 25997 26018 25116 25534 25952 26439 27291 27935 27840 27599 28527 27774 27234 26671 26433 27157 27652 28245 28608 28654 29635 29158 29015 29859 29304 28664 29196 29357 29491 28879 28384 28671 28775 29199 28752 2819...
output:
2.3500000000 6.1639118457 6.0636856369 68.0942760943 7291.0000000000 7291.0000000000 7291.0000000000 7291.0000000000 7291.0000000000 1.1470588235 7291.0000000000 7291.0000000000 6.1554332875 14.2012288786 40.8383838384 7291.0000000000 6.0719131615 40.3291770574 7291.0000000000 17.2806539510 7291.000...
result:
ok
Test #10:
score: 0
Accepted
time: 1ms
memory: 3772kb
input:
8 2 0 0 10 30 60 45 75 65 30 2.0 3.1
output:
3.0000000000 impossible
result:
ok
Test #11:
score: 0
Accepted
time: 47ms
memory: 4364kb
input:
10000 47 54154 53676 52932 53223 52594 51885 50915 51169 51488 50741 51691 52139 52229 52749 53735 54628 54039 54907 55611 56405 55859 56650 55661 54850 55821 54918 54077 54898 54876 54525 55220 54988 55245 55262 54299 54257 54652 53954 54268 54840 55723 56141 56926 57012 57805 57540 56832 55859 564...
output:
81.7518610422 10000.0000000000 10000.0000000000 10000.0000000000 10000.0000000000 10000.0000000000 6.1908771930 10000.0000000000 130.3790322581 10000.0000000000 4.3439153439 10000.0000000000 20.4540540541 2.1750000000 10000.0000000000 10000.0000000000 4.4139784946 10000.0000000000 6.1952247191 10000...
result:
ok
Test #12:
score: 0
Accepted
time: 372ms
memory: 7432kb
input:
50000 50 3760328 3760197 3760003 3759815 3759707 3759570 3759431 3759282 3759160 3758998 3758834 3758663 3758552 3758359 3758258 3758066 3757915 3757720 3757537 3757417 3757317 3757204 3757069 3756966 3756788 3756673 3756547 3756375 3756231 3756062 3755867 3755766 3755567 3755402 3755218 3755085 375...
output:
49939.9657534247 49611.6153846154 49284.0680628272 48961.1393034826 48646.9181818182 48330.7831325301 48019.7536231884 47712.7142857143 47406.6688311688 47107.8953488372 46812.6213017752 46523.9319727891 46236.3228346457 45957.0443349754 45673.1618497110 45397.3167701863 45121.7229729730 44855.46625...
result:
ok
Test #13:
score: 0
Accepted
time: 772ms
memory: 11236kb
input:
100000 50 7496165 7496059 7495939 7495810 7495706 7495527 7495379 7495197 7495003 7494806 7494616 7494443 7494332 7494190 7494063 7493890 7493752 7493608 7493503 7493362 7493197 7493070 7492944 7492815 7492631 7492528 7492417 7492248 7492062 7491913 7491801 7491697 7491573 7491392 7491206 7491082 74...
output:
100000.0000000000 99415.6754966887 98762.5792682927 98121.2832369942 97489.0737704918 96855.3177083333 96239.1773399015 95624.3913043478 95020.0242718447 94425.9891891892 93834.3741007194 93248.8865248227 92666.1350000000 92089.3057324841 91528.7571428571 90974.2606382979 90425.9714285714 89881.6989...
result:
ok
Test #14:
score: 0
Accepted
time: 42ms
memory: 10784kb
input:
100000 4 70569 69671 70010 70356 71246 70503 70339 70562 69569 69788 69586 69557 69489 69571 68633 69321 69696 70055 69822 70430 71072 70716 70786 70462 70957 70653 69782 69754 69103 70038 70414 70779 70527 71364 71956 71937 70948 70024 70856 70596 69947 70376 71161 72114 71117 71288 72064 72475 718...
output:
100000.0000000000 4.3105590062 5.1261261261 100000.0000000000
result:
ok
Test #15:
score: 0
Accepted
time: 42ms
memory: 4380kb
input:
10000 50 333333325 333333316 333333303 333333293 333333278 333333268 333333263 333333249 333333242 333333236 333333225 333333217 333333208 333333196 333333182 333333174 333333163 333333158 333333145 333333128 333333128 333333113 333333099 333333088 333333081 333333075 333333065 333333058 333333044 3...
output:
10000.0000000000 10000.0000000000 10000.0000000000 10000.0000000000 10000.0000000000 10000.0000000000 10000.0000000000 10000.0000000000 10000.0000000000 10000.0000000000 10000.0000000000 10000.0000000000 10000.0000000000 10000.0000000000 10000.0000000000 10000.0000000000 10000.0000000000 10000.00000...
result:
ok
Test #16:
score: 0
Accepted
time: 746ms
memory: 10780kb
input:
100000 50 999996515 999996352 999996218 999996034 999995850 999995714 999995550 999995429 999995242 999995100 999994910 999994720 999994542 999994431 999994281 999994133 999993959 999993777 999993588 999993444 999993334 999993204 999993035 999992924 999992768 999992667 999992544 999992430 999992289 ...
output:
100000.0000000000 99352.9344262295 98706.2941176471 98064.5769230769 97427.0965517241 96801.3157894737 96185.0914285714 95573.4258064516 94978.3739130435 94389.6989247312 93803.5595854922 93221.5130434783 92649.1646341463 92078.8950000000 91516.9320388349 90965.7500000000 90422.1014492754 89882.1600...
result:
ok
Test #17:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
2 2 0 30 30 3.0 2.0
output:
1.0000000000 1.5000000000
result:
ok
Test #18:
score: 0
Accepted
time: 10ms
memory: 4140kb
input:
7284 11 36420 35566 35213 34942 34713 34512 34330 34163 34007 33861 33722 33591 33465 33345 33229 33117 33009 32905 32803 32704 32608 32514 32422 32333 32245 32160 32075 31993 31912 31833 31755 31678 31602 31528 31455 31382 31311 31241 31172 31104 31037 30970 30904 30840 30775 30712 30649 30587 3052...
output:
7284.0000000000 3642.0000000000 3296.0000000000 1718.0000000000 824.0000000000 409.0000000000 303.0000000000 95.0000000000 28.0000000000 21.0000000000 1.0000000000
result:
ok
Test #19:
score: 0
Accepted
time: 7ms
memory: 3932kb
input:
5040 10 0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430 440 450 460 470 480 490 500 510 520 530 540 550 560 570 580 590 600 610 620 630 640 650 660 670 680 690 700 710 720 730 740 750...
output:
5040.0000000000 2520.0000000000 1680.0000000000 1260.0000000000 1008.0000000000 840.0000000000 720.0000000000 630.0000000000 560.0000000000 504.0000000000
result:
ok
Test #20:
score: 0
Accepted
time: 1235ms
memory: 10752kb
input:
100000 50 15015 30030 15015 30030 15015 30030 15015 30030 15015 30030 15015 30030 15015 30030 15015 30030 15015 30030 15015 30030 15015 30030 15015 30030 15015 30030 15015 30030 15015 30030 15015 30030 15015 30030 15015 30030 15015 30030 15015 30030 15015 30030 15015 30030 15015 30030 15015 30030 15...
output:
100000.0000000000 100000.0000000000 100000.0000000000 100000.0000000000 100000.0000000000 100000.0000000000 100000.0000000000 100000.0000000000 100000.0000000000 100000.0000000000 100000.0000000000 100000.0000000000 100000.0000000000 100000.0000000000 100000.0000000000 100000.0000000000 100000.00000...
result:
ok
Test #21:
score: 0
Accepted
time: 1493ms
memory: 11216kb
input:
99732 50 911857101 441877798 143006716 819152721 490297116 376684424 689879332 119445452 883109696 410738441 895439043 446157436 598896085 907059032 296576477 773474432 686052352 65974399 69612661 723640393 790838891 537383465 870627577 332367060 385955757 682362572 525729684 848124936 869983210 674...
output:
99730.2371594229 99730.2324877551 99730.1730908739 99730.2752001628 99730.1080213382 99730.3058997284 99729.0483575437 99729.0763704400 99729.4360574271 99730.0786566524 99729.9593449977 99730.2595166963 99729.2388455490 99729.8540147241 99729.4584679172 99729.3116793904 99729.7273945833 99730.21146...
result:
ok
Test #22:
score: 0
Accepted
time: 287ms
memory: 10852kb
input:
99836 50 85 70 0 68 16 5 97 90 6 59 27 59 87 6 75 87 3 49 43 61 73 70 78 23 52 55 50 27 64 44 93 18 62 38 25 84 100 0 66 47 20 100 34 97 20 56 55 82 68 78 78 58 95 36 53 92 77 100 9 27 14 65 1 1 10 5 61 26 22 86 9 48 18 5 1 89 20 67 39 41 99 15 58 21 86 38 68 15 66 41 88 38 77 41 50 67 48 26 51 66 5...
output:
impossible impossible impossible impossible impossible 99836.0000000000 99836.0000000000 99836.0000000000 impossible 2.3809523810 99836.0000000000 impossible impossible impossible impossible impossible impossible impossible 3.3225806452 99836.0000000000 impossible 99836.0000000000 99836.0000000000 9...
result:
ok
Test #23:
score: 0
Accepted
time: 1461ms
memory: 10716kb
input:
99183 50 964230526 132957742 342381630 333187261 560592466 676940895 87186775 684663916 521776721 651043246 161142378 56406444 928585185 267581525 58992338 285499679 587916122 513107306 500818299 497313290 502872368 146394763 50719356 997386166 297992233 135871216 669799075 126396155 287409523 94873...
output:
99182.9315634867 99182.9081778404 99182.9808404205 99182.9455232911 99182.9247625578 99182.8106979946 99183.0000000000 99182.9826301405 99182.9103255013 99182.9714145625 99182.9697441575 99182.9012576002 99182.8101014233 99182.9193934041 99183.0000000000 99182.8636735541 99182.9257170741 99182.82072...
result:
ok
Test #24:
score: 0
Accepted
time: 1451ms
memory: 10684kb
input:
99552 50 792262023 988360152 980724637 48309850 20067731 772783473 98160605 984372097 300078336 952265416 223916919 242029819 746223745 478317372 714947344 529196688 537251626 24260617 31530413 944828609 795486943 939382988 52679842 113669375 759578594 989055434 585146225 970293816 98251234 90097523...
output:
99551.0608302781 99549.1239521993 99551.0115595526 99551.1553633997 99551.0999128543 99551.0588260442 99549.1112471888 99551.0878874430 99551.0259232167 99551.1461773111 99551.0923969719 99551.1528581027 99549.0659789424 99549.1360166240 99551.0593271027 99549.1276889677 99549.0689683536 99551.12663...
result:
ok
Test #25:
score: 0
Accepted
time: 925ms
memory: 11144kb
input:
99462 50 63051 52949 22691 38321 77711 86744 3982 6292 72258 73916 75179 93671 94690 61643 42874 22706 14463 38237 2225 57815 94482 81036 16157 60456 64605 43276 82008 86340 39672 57245 84837 99554 7932 9051 98419 56509 30172 36473 23912 66132 62466 38503 55416 45114 63747 96921 62471 43436 52166 93...
output:
515.0021960987 125.0073876788 128.0028286307 99462.0000000000 179.2326869806 99462.0000000000 99462.0000000000 975.0181606234 99462.0000000000 99462.0000000000 181.0166234815 99462.0000000000 125.0113513856 105.2594936709 196.0436418360 14267.0012538798 99462.0000000000 99462.0000000000 107.09892473...
result:
ok
Test #26:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
2 2 0 0 30 3.0 2.0
output:
1.0000000000 1.5000000000
result:
ok
Test #27:
score: 0
Accepted
time: 1ms
memory: 3776kb
input:
2 1 20 10 30 0.0
output:
2.0000000000
result:
ok
Test #28:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
10 7 42 42 42 42 42 42 42 42 42 42 42 -100.0 -50.0 -0.1 0.0 0.1 50.0 100.0
output:
10.0000000000 10.0000000000 10.0000000000 10.0000000000 impossible impossible impossible
result:
ok