QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#136297#2417. Height ProfileBUET_TEAM_ONEAC ✓1493ms11236kbC++232.4kb2023-08-07 19:30:492023-08-07 19:30:50

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-07 19:30:50]
  • 评测
  • 测评结果:AC
  • 用时:1493ms
  • 内存:11236kb
  • [2023-08-07 19:30:49]
  • 提交

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();
}

Details

Tip: Click on the bar to expand more detailed information

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