QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#488412#4568. Budget Distributionarnold518AC ✓269ms38772kbC++172.9kb2024-07-24 01:40:202024-07-24 01:40:20

Judging History

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

  • [2024-07-24 01:40:20]
  • 评测
  • 测评结果:AC
  • 用时:269ms
  • 内存:38772kb
  • [2024-07-24 01:40:20]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

typedef long double ld;
typedef pair<ld, ld> pdd;

const int MAXN = 5e4;
const int MAXQ = 3e5;

const ld eps = 1e-7;

int N, Q;
vector<pll> A[MAXN+10];
pll B[MAXQ+10];
ld xsum, sqcsum, fsum, psum;
ld ans[MAXQ+10];

struct Data
{
    ld slp, dsqc, dx;
    ld dp, df;
    bool operator < (Data ot) const { return slp < ot.slp; }
};

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    ll sum=0;
    scanf("%d%d", &N, &Q);

    vector<Data> V;
    for(int i=1; i<=N; i++)
    {
        int t;
        scanf("%d", &t);
        A[i]=vector<pll>(t);

        ll psum=0, csum=0;
        for(int j=0; j<t; j++) scanf("%lld", &A[i][j].first), csum+=A[i][j].first;
        for(int j=0; j<t; j++) scanf("%lld", &A[i][j].second), psum+=A[i][j].second;
        sum+=csum;

        sort(A[i].begin(), A[i].end(), [&](pll p, pll q)
        {
            return p.first*q.second < q.first*p.second;
        });

        ld bef=0;
        ll cval=csum, pval=psum;
        bool flag=false;
        for(int j=0; j<t; j++)
        {
            ld l=bef, r=(ld)A[i][j].first/A[i][j].second*psum;
            l=max(l, (ld)csum);
            if(l+eps < r)
            {
                ld slpl = -cval/l/l, slpr = -cval/r/r;
                ld fl = cval/l-(ld)pval/psum, fr = cval/r-(ld)pval/psum;
                // printf("%.10Lf %.10Lf : %.10Lf %.10Lf / %.10Lf %.10Lf / %lld %lld %lld\n", l, r, slpl, slpr, fl, fr, cval, pval, psum);
                if(!flag)
                {
                    flag=true;
                    xsum+=l;
                    fsum+=fl;
                }
                V.push_back({slpl, sqrt((ld)cval), -l, (ld)pval/psum, -fl});
                V.push_back({slpr, -sqrt((ld)cval), r, -(ld)pval/psum, fr});
            }

            cval-=A[i][j].first;
            pval-=A[i][j].second;
            bef=r;
        }
        if(!flag) xsum+=max(bef, (ld)csum);
    }
    for(int i=1; i<=Q; i++)
    {
        scanf("%lld", &B[i].first);
        B[i].first+=sum;
        B[i].second=i;
    }
    sort(B+1, B+Q+1);

    sort(V.begin(), V.end());
    for(int i=0, j=1; i<V.size(); i++)
    {
        auto [slp, dsqc, dx, dp, df] = V[i];
        ld x=(sqcsum+dsqc)/sqrt(-slp)+(xsum+dx);
        // printf("!%.20Lf : %.20Lf\n", slp, x);
        for(; j<=Q && B[j].first<=x; j++)
        {
            // printf("ANS %lld %lld => %.10Lf %.10Lf %.10Lf\n", B[j].second, B[j].first, sqcsum, psum, fsum);
            if(sqcsum < eps) ans[B[j].second]=fsum;
            else ans[B[j].second]=sqcsum*sqcsum/(B[j].first-xsum)-psum+fsum;
        }

        sqcsum+=dsqc;
        xsum+=dx;
        fsum+=df;
        psum+=dp;
    }

    for(int i=1; i<=Q; i++) printf("%.20Lf\n", ans[i]*2);
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 5956kb

input:

1 5
3 1 7 10 700 400 100
0 2 10 50 102

output:

1.05555555555555555551
0.86666666666666666651
0.54761904761904761906
0.12745098039215686281
0.00000000000000000005

result:

ok 5 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 5200kb

input:

2 5
3 10 70 100 700 400 100
3 10 30 100 700 400 100
2 10 50 70 110

output:

2.29670329670329670347
2.21677634065518756683
1.86901673626003215416
1.73015873015873015853
1.52713178294573643417

result:

ok 5 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 6148kb

input:

10 10
2 33942 868 371 78
2 76858 41608 333 100
2 6654 20321 170 203
2 2620 63358 632 53
2 93065 61561 594 212
2 57474 542 813 559
2 40721 17760 290 976
2 46703 85826 255 366
2 46854 97247 875 814
2 86728 83989 602 306
201032820943 922351084935 360042197511 441040805811 822857993607 196200869890 4856...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 6416kb

input:

10 10
2 96134 53888 702 380
2 13325 18733 529 846
2 88540 54362 938 703
2 8808 55334 591 19
2 44013 54721 319 891
2 83136 55364 214 73
2 20391 6867 838 8
2 26623 38206 497 763
2 17952 8445 377 586
2 44642 45084 728 45
79 70 52 33 63 42 12 63 43 19

output:

4.47092640798093454409
4.47138754315995747392
4.47231075500160071834
4.47328662061820361709
4.47174642073196838181
4.47282419364680018659
4.47436684259907563191
4.47174642073196838181
4.47277283230517053170
4.47400657777277784097

result:

ok 10 numbers

Test #5:

score: 0
Accepted
time: 1ms
memory: 6964kb

input:

10 10
2 87040 85595 968 661
2 30804 2371 595 360
2 67653 67814 918 546
2 41321 35253 782 456
2 87902 48810 187 121
2 42170 84373 530 949
2 50987 54778 671 987
2 14728 42286 11 621
2 58533 75318 331 777
2 16391 57471 903 6
59864 120 8708 29592 32313 33728 70753 22703 10343 23788

output:

2.60343780003182455308
3.80230065581593389308
3.42288753536892115356
2.96016813271937869302
2.92026983039578633735
2.90046122302335462667
2.49844328844343501177
3.07327149176194822284
3.36762279199016834530
3.05418759781712122756

result:

ok 10 numbers

Test #6:

score: 0
Accepted
time: 1ms
memory: 6700kb

input:

10 10
2 55721 79321 580 343
2 95806 49722 805 940
2 78827 17939 667 94
2 6559 95072 787 101
2 94219 75884 552 449
2 30793 62126 870 399
2 85442 23970 408 302
2 1278 2598 862 62
2 31318 32132 323 412
2 58132 71731 139 922
3906840 989184 7399265 8741239 2517664 9283266 5589494 6287477 4787549 4589132

output:

0.00000000000000000000
0.22562556533133194457
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000

result:

ok 10 numbers

Test #7:

score: 0
Accepted
time: 1ms
memory: 5132kb

input:

10 1000
2 77028 12264 551 939
2 78089 30777 523 797
2 52960 82253 148 858
2 31700 74778 830 751
2 82878 16882 965 56
2 45145 65715 165 802
2 45515 12564 949 925
2 74172 24959 285 684
2 82124 35743 748 30
2 57875 4015 855 611
735264331681 371600467165 94562142784 569058824359 478028793676 54038716428...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0...

result:

ok 1000 numbers

Test #8:

score: 0
Accepted
time: 1ms
memory: 6612kb

input:

10 1000
2 3938 22415 871 82
2 27631 97743 165 825
2 65967 18034 62 901
2 32242 10555 911 686
2 8940 50904 300 731
2 68995 92862 315 731
2 88209 67039 379 38
2 21342 97668 185 932
2 87548 79592 402 31
2 58250 93518 738 332
1 95 82 41 37 90 75 42 76 12 57 100 26 41 85 6 15 37 34 61 42 51 69 5 14 30 76...

output:

6.10739851392914860585
6.10135266606346796494
6.10218623196396171664
6.10482054917004762426
6.10507799397209895923
6.10167317133866879365
6.10263541481360199123
6.10475620016146517744
6.10257123126722576681
6.10668879382639038069
6.10379154980221199723
6.10103228194854203944
6.10578636975547562465
6...

result:

ok 1000 numbers

Test #9:

score: 0
Accepted
time: 0ms
memory: 6704kb

input:

10 1000
2 5140 93191 993 507
2 49021 71125 253 668
2 54110 90050 237 705
2 14347 68749 921 989
2 90266 34358 823 341
2 75716 40108 379 298
2 75242 1960 390 505
2 82368 59940 873 599
2 80119 25572 458 269
2 77505 23084 473 542
13582 50935 29056 56674 60779 57858 54777 64188 71802 62584 98903 19513 26...

output:

4.25314670483105375202
3.62459972041897065804
3.97311847478146721994
3.54016727012256042094
3.48116929613913928020
3.52303734110361567639
3.56781702564544696819
3.43290250523067033608
3.32731273049610648063
3.45553524606459716790
2.97462098848839042115
4.14213269441308574483
4.02466255299675230214
3...

result:

ok 1000 numbers

Test #10:

score: 0
Accepted
time: 1ms
memory: 5052kb

input:

10 1000
2 63317 53050 130 281
2 64560 28892 410 881
2 1063 11155 826 49
2 40055 59506 424 645
2 12471 7521 963 271
2 19232 77975 924 545
2 99920 71689 222 682
2 94741 8756 840 370
2 48868 73259 816 882
2 66849 33301 483 146
9873316 4084979 2160366 7640555 1658999 4484798 3942725 8537680 7071378 1801...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
1.77966520361220030891
0.00000000000000000000
0.00000000000000000000
0...

result:

ok 1000 numbers

Test #11:

score: 0
Accepted
time: 102ms
memory: 11928kb

input:

10 300000
2 80591 44947 481 327
2 75950 2449 866 938
2 99608 77677 797 190
2 58139 15935 651 10
2 44816 33174 358 436
2 38004 26636 226 565
2 469 38698 415 136
2 42979 87602 981 867
2 60596 22147 89 853
2 48278 17909 953 392
692991526086 159941543361 696799547314 839250682232 929834822694 5575324243...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0...

result:

ok 300000 numbers

Test #12:

score: 0
Accepted
time: 103ms
memory: 14428kb

input:

10 300000
2 14727 60185 203 943
2 957 83853 755 274
2 34549 74057 591 60
2 36606 42995 780 234
2 99519 45408 758 164
2 90464 79714 893 283
2 10282 71750 94 219
2 36569 58396 705 759
2 43097 68284 739 347
2 92033 75118 481 318
161797 388092 583550 632465 602460 390359 708606 645995 802797 718316 6441...

output:

3.23039680929384285515
1.91148649099842907651
1.17754177935215114672
1.02936802206749226311
1.11881696859662318935
1.90144288807471007418
0.82354684178287924587
0.99064168222106742617
0.60706971982720216808
0.79928260037849300243
0.99580489108579604244
4.05756039164041051870
0.28456347418030803839
5...

result:

ok 300000 numbers

Test #13:

score: 0
Accepted
time: 104ms
memory: 14476kb

input:

10 300000
2 24657 78396 784 707
2 82124 78980 350 675
2 49942 96873 793 420
2 51590 81596 443 843
2 95550 24127 983 681
2 58878 89659 891 881
2 13331 4486 344 639
2 40425 42504 785 234
2 79181 50756 130 948
2 18402 76432 814 229
9082979 7690187 3589112 3211595 8594440 3257496 1723111 3336064 9781022...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0...

result:

ok 300000 numbers

Test #14:

score: 0
Accepted
time: 1ms
memory: 5068kb

input:

10 10
5 52610 28731 22847 35575 92477 123 900 153 973 448
5 79020 21023 59748 35335 70749 982 566 736 644 781
5 12526 77062 53974 90431 44804 346 958 583 184 581
3 80317 48431 45398 740 307 120
3 68944 27423 17637 905 271 444
2 43575 34316 375 221
5 49626 4091 68522 85021 46323 526 728 120 156 10
3 ...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000

result:

ok 10 numbers

Test #15:

score: 0
Accepted
time: 1ms
memory: 5068kb

input:

10 10
4 65110 95449 82698 71008 894 648 27 228
5 60011 10464 57083 68265 68445 36 90 754 229 247
3 21233 63487 79092 912 892 495
4 4035 24700 13745 33736 266 456 164 626
4 27592 83673 71525 32997 202 865 529 751
4 26109 14552 17478 72487 443 788 339 241
5 37454 13011 7612 9873 80264 117 650 120 349 ...

output:

6.68934507481089864114
6.69103208516074921377
6.69145430801581866161
6.69068451356429674641
6.68944422748841709993
6.69150399367389897391
6.68998975306917791767
6.68989054319894144119
6.69090793779657685286
6.69013858738252976868

result:

ok 10 numbers

Test #16:

score: 0
Accepted
time: 1ms
memory: 6304kb

input:

10 10
3 9723 45483 41663 180 412 187
4 97649 15044 76931 1479 971 143 884 205
4 98370 39080 92343 85645 864 528 311 139
3 87812 41408 3618 520 439 162
4 57153 91809 20722 52851 904 299 271 644
2 94086 60318 194 512
2 46688 66547 603 750
4 44879 94379 75684 3996 260 291 680 444
4 94896 69948 61990 90...

output:

4.06285971851362018650
3.61720112404760637268
3.40814299590223935437
3.31052462702862295568
4.59471965814206529267
3.77527328877383244244
3.57901636214102806285
3.89520612808622194436
3.30137355949046418365
3.33751665774453227489

result:

ok 10 numbers

Test #17:

score: 0
Accepted
time: 1ms
memory: 5980kb

input:

10 10
4 15609 65721 77099 1645 403 541 288 785
4 44486 61984 94869 40006 68 826 483 561
3 28190 3593 87641 8 570 561
2 55124 97214 146 846
5 78455 77453 36526 32533 89431 704 182 808 163 167
3 85119 41444 46422 289 157 887
5 78190 8611 92893 60931 69904 332 580 194 151 778
4 68482 41077 79758 39706 ...

output:

0.00135952231493231617
0.20937647005878868203
1.43785099543817420416
0.02337438415090288453
0.03049223060604146364
0.04851591018621306749
0.00616500546605696599
1.77284166502091737800
0.71794203530412529818
0.76041533876476188024

result:

ok 10 numbers

Test #18:

score: 0
Accepted
time: 0ms
memory: 5140kb

input:

10 1000
3 98857 46905 48686 222 634 335
4 95418 14008 68547 90033 749 869 494 849
4 6152 32171 54190 98101 313 223 685 17
5 23928 41942 49688 26798 16050 245 922 330 731 978
5 4485 53360 81073 78705 83422 438 155 989 720 906
4 5745 17815 55961 23066 370 607 561 340
3 75189 75062 1657 742 843 70
2 27...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0...

result:

ok 1000 numbers

Test #19:

score: 0
Accepted
time: 0ms
memory: 6928kb

input:

10 1000
2 98267 69661 589 273
3 70747 34816 70253 546 949 873
2 47435 94946 490 355
3 61549 40110 24381 963 983 422
2 98028 48962 376 672
5 9351 67283 26704 76201 87921 580 938 70 688 339
2 52842 51624 495 729
4 47695 32102 50092 21172 722 198 57 107
5 18679 37632 55787 63933 77463 455 836 217 188 3...

output:

4.67212724503420064222
4.67287297814351092022
4.67236492639927926060
4.67282972494952581442
4.67282972494952581442
4.67285135120342693315
4.67285135120342693315
4.67244056967935775682
4.67250541346075171480
4.67210564174856721274
4.67210564174856721274
4.67298112313781699402
4.67257026341309120426
4...

result:

ok 1000 numbers

Test #20:

score: 0
Accepted
time: 1ms
memory: 7076kb

input:

10 1000
2 6799 39344 364 707
2 21377 26908 660 54
4 35458 88922 81786 81556 329 925 772 410
5 40965 18428 95181 48238 18322 395 164 843 477 826
5 76116 34444 24971 19277 1071 882 414 315 29 140
3 7302 29915 55237 538 970 505
4 94740 6056 69454 12775 429 971 234 617
4 61028 28738 81858 7554 487 199 2...

output:

4.80260467748619341959
5.32992862908591760089
5.06684356470763643497
5.79331292046919821108
5.04916554616447654010
5.60618669786247208727
5.39405683777481354240
5.40599421411392660683
5.29525779291448930614
5.08779934740829058561
5.07434644048388972231
4.87487484891649113742
5.04750704031867332422
5...

result:

ok 1000 numbers

Test #21:

score: 0
Accepted
time: 1ms
memory: 6304kb

input:

10 1000
4 9470 97718 45626 90814 297 342 594 796
4 54273 99935 5000 36382 488 728 886 700
4 7703 15452 73294 49935 241 542 332 263
5 59748 81651 87470 32404 45271 698 371 461 215 197
3 54659 93335 63302 716 487 255
4 88462 47791 98874 89496 898 790 982 999
2 79129 486 203 72
4 81139 5321 83671 2050 ...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.38218936897611095491
0.00435348153805720297
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.04527784820087670632
0.00000000000000000000
1...

result:

ok 1000 numbers

Test #22:

score: 0
Accepted
time: 91ms
memory: 11752kb

input:

10 300000
2 32856 36826 318 704
2 22612 24781 268 229
3 75564 78094 35035 408 98 67
5 61112 71175 5065 72192 91429 651 388 723 655 328
3 14292 33117 73323 719 53 549
4 97674 16169 71135 32705 470 129 938 789
3 13520 42886 69152 794 487 249
5 93676 44922 58923 50471 12587 24 497 36 119 623
2 35576 17...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0...

result:

ok 300000 numbers

Test #23:

score: 0
Accepted
time: 93ms
memory: 14572kb

input:

10 300000
5 69763 68588 37790 74294 64102 375 387 677 91 229
3 45029 88460 39178 274 862 993
5 91656 7847 36915 44992 61893 240 42 486 545 305
5 84176 38849 27609 72636 82391 861 360 392 286 219
2 27044 48829 834 168
5 71695 63744 16657 95621 12068 509 16 317 664 5
3 46535 45274 69554 915 708 598
5 ...

output:

3.88643698652861288405
4.82840232493903669195
4.24152441998334705456
2.02026612389408065677
2.01630133074536681227
2.33626663609383035457
2.27782931435554376019
3.11526665451674578209
1.82979362618966833018
2.66384960682348132790
1.99675389392608617007
2.33578404796919406440
1.81485185331520220407
1...

result:

ok 300000 numbers

Test #24:

score: 0
Accepted
time: 113ms
memory: 14564kb

input:

10 300000
5 70858 61540 67679 62486 9936 483 649 740 143 114
4 96931 62820 26452 34549 441 147 721 803
2 68161 33955 804 951
2 59834 90030 894 81
2 56615 17480 610 502
2 78398 36283 741 360
2 34933 88158 891 150
5 56539 79406 11934 45198 79211 759 799 203 482 996
2 85259 87478 634 354
5 20179 69266 ...

output:

0.06989773071866639049
0.34796377176475520762
1.17405616426215384570
0.00000000000000000000
0.09575208585497061979
2.69261538722955361428
0.02607451295066158023
0.75935775598174401404
0.00000000000000000000
0.00223190348749168999
0.06224565273054857442
0.03424387324485218526
0.55459724548471635893
0...

result:

ok 300000 numbers

Test #25:

score: 0
Accepted
time: 162ms
memory: 14568kb

input:

1000 300000
2 84250 9940 822 333
3 11817 1621 66723 783 475 855
3 14193 51801 80603 459 913 781
3 45892 79597 51991 534 693 429
5 31168 83082 12880 52743 15259 316 376 223 547 600
2 66767 76783 702 846
2 22426 51907 861 643
2 62103 34470 121 276
5 93903 43385 18077 93366 88699 429 180 397 222 709
3 ...

output:

600.34352383840747813259
600.34021325477776181989
600.35920169440890376000
600.33835625084748177649
600.34352383840747813259
600.34809531135355903375
600.35562481274050949942
600.34228098010161023268
600.35730634191557109069
600.34352383840747813259
600.35751674652671938670
600.34580675551505507537
...

result:

ok 300000 numbers

Test #26:

score: 0
Accepted
time: 175ms
memory: 14764kb

input:

1000 300000
5 81599 60638 24241 47364 81909 211 415 908 603 571
5 55972 79849 82630 81750 57714 311 278 443 53 455
3 35752 39134 36254 575 710 106
4 79138 64703 43257 88775 135 693 874 426
2 57132 92509 461 144
4 53871 2386 53742 72256 570 223 323 833
3 43191 33069 43115 105 407 656
3 56083 7682 724...

output:

589.82994281015757942477
589.94254593040151307681
592.68007475301766490139
589.90447242639486968852
590.02750815412693097262
595.45012468273167044464
592.67914039440980611406
594.21691601574644764350
591.33450906742962410734
589.84846827146404618647
592.84614973442409779913
592.02807811556752964899
...

result:

ok 300000 numbers

Test #27:

score: 0
Accepted
time: 174ms
memory: 14552kb

input:

1000 300000
3 98060 15595 60475 846 131 849
4 66344 8428 20435 66985 575 855 613 222
2 36055 55773 599 183
4 61642 50861 78593 34743 130 701 352 353
2 73921 9075 852 993
3 20419 64920 59373 324 222 440
5 68121 75295 19210 48725 14102 356 763 277 104 935
2 72642 25128 310 127
5 99812 13972 76300 3101...

output:

479.68090979181648786378
559.88054278597716911792
551.50105802641606095316
485.14957706838426054752
516.10130865300612007518
504.08906983652728689416
549.83378576331719450598
589.05348203090675740512
481.84203423923108988713
530.36470167734917990909
489.70304391167838797827
515.25852626240773346478
...

result:

ok 300000 numbers

Test #28:

score: 0
Accepted
time: 187ms
memory: 14608kb

input:

1000 300000
2 32732 44059 376 504
4 79598 95119 972 37471 531 149 313 55
2 19476 24603 354 497
3 95666 14230 18089 234 800 970
3 16475 96750 44845 501 607 758
5 89297 37326 45706 97640 45959 921 284 765 629 375
5 38973 6900 96331 41294 19691 914 171 481 241 257
4 8185 35930 27678 41856 517 168 11 77...

output:

301.55518619080272033073
404.78693509308218662079
261.71174726434133411823
408.27349855191934063781
234.06815068477703187244
344.01530113169793498318
312.43287615013879054970
172.18060386067621538031
330.78424829765453088481
164.60737996923023601648
222.39138009937654966164
238.43479866080167857423
...

result:

ok 300000 numbers

Test #29:

score: 0
Accepted
time: 147ms
memory: 14548kb

input:

1000 300000
5 85721 60340 51957 49467 16065 981 982 873 292 800
5 3773 11734 48381 35228 15873 359 929 25 860 859
3 47216 44378 45298 121 948 274
5 61083 39739 73855 37414 37561 806 913 551 268 37
2 14796 92922 649 224
2 25163 44185 896 717
5 92350 93841 42670 30464 43630 30 171 954 700 885
5 24436 ...

output:

2.04677999725335437180
2.49151549411916838680
0.09967372651256856799
0.10047172686206598448
4.20574549025029497881
1.49132164489911691273
0.11280569075004646449
3.90586458805813921424
0.22683245020159569796
0.09369607927771916841
102.24300604206656312156
0.04420631752441755424
0.03524458765387212731...

result:

ok 300000 numbers

Test #30:

score: 0
Accepted
time: 113ms
memory: 14516kb

input:

1000 300000
4 89993 23538 39615 38540 517 850 610 508
5 26964 77519 2269 35303 27339 111 467 83 301 211
4 96202 37228 23231 24309 986 895 345 766
5 86769 51230 10007 66718 40625 94 928 842 161 99
4 64925 34472 41278 11882 369 800 930 824
4 35320 66791 4089 4477 162 504 641 637
3 64053 65753 44948 54...

output:

0.00000000000000000000
0.00000000000000000000
247.71522474390423537716
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00177859345543598228
0.00000000000000000000
0.93533435595589555216...

result:

ok 300000 numbers

Test #31:

score: 0
Accepted
time: 108ms
memory: 14500kb

input:

1000 300000
5 30466 86414 62578 7594 75197 417 512 738 361 891
3 34948 70502 10387 972 472 515
4 28405 12587 30671 48914 705 341 290 368
3 46194 8786 26901 815 713 982
3 36300 93352 77447 982 16 853
3 57450 49474 62910 631 654 725
4 12989 99690 41855 33415 980 965 53 586
2 55434 93614 433 565
3 3646...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0...

result:

ok 300000 numbers

Test #32:

score: 0
Accepted
time: 107ms
memory: 12688kb

input:

1000 300000
5 93664 30968 51651 11046 95770 237 146 538 821 334
3 67028 49460 15270 270 388 886
3 53800 60523 15341 928 444 29
4 36765 85066 73638 34472 584 671 17 46
2 36316 4130 340 340
3 74686 98983 66079 940 86 268
4 15653 46488 18760 17235 399 30 382 840
2 8052 37957 683 482
3 63480 1002 41695 ...

output:

0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
6.88314754789300774392
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0...

result:

ok 300000 numbers

Test #33:

score: 0
Accepted
time: 241ms
memory: 32496kb

input:

50000 300000
2 19162 4275 229 580
2 5047 79258 832 762
5 30493 57246 19965 83085 41107 650 192 558 865 868
3 5163 41326 17640 52 922 20
3 3259 67604 84435 954 40 136
4 20477 32119 27145 8205 138 115 131 754
3 79209 9 74084 537 328 594
3 2022 80071 23608 345 703 527
4 54374 7035 24717 39188 796 214 7...

output:

30213.11388086778423023304
30213.09154953006751398448
30213.10033403790309414205
30213.08694342448152703184
30213.12192113627398803999
30213.11106070895511876984
30213.12620782289814691524
30213.12097137819717040941
30213.12668541605318672794
30213.11623798513397076704
30213.09293368595236550789
302...

result:

ok 300000 numbers

Test #34:

score: 0
Accepted
time: 249ms
memory: 32556kb

input:

50000 300000
4 95746 46633 48769 95672 74 953 72 480
4 41325 6706 91366 92453 574 737 69 307
2 55433 5100 462 78
2 13500 63369 818 699
3 3355 90534 24139 171 688 421
4 38417 45136 99490 59886 397 39 920 296
4 46963 13880 40228 94288 74 686 670 825
2 13756 27722 817 965
3 62627 47895 59766 477 292 74...

output:

30244.20141254880661030313
30245.59303051720774213607
30253.28174621079582884420
30240.96532281630575944575
30247.25665905027510405034
30251.50320914267700622702
30252.30321213642781863484
30246.01980796842306808969
30254.96122228830409817135
30244.14911977438819867814
30249.20428458721526965292
302...

result:

ok 300000 numbers

Test #35:

score: 0
Accepted
time: 239ms
memory: 31508kb

input:

50000 300000
3 16759 72826 84591 307 169 803
3 66480 96374 92817 275 370 696
5 93576 20421 36794 40572 47645 487 191 87 931 412
3 8119 84137 17276 748 901 835
5 7434 13951 50805 4129 31372 126 212 992 919 97
2 19873 79348 993 412
4 46127 75115 23135 23370 488 353 137 573
2 49961 58919 352 415
5 9653...

output:

30083.18003795740554906502
30311.66780723775482719873
29963.73990085484907552882
30140.69320521244396360316
29961.92730654739725970614
30032.38253707269214842768
30238.86880164189379804895
30224.39739487905586123873
30203.91891776603189789796
30092.89395261516145829717
30142.87112661381007683303
299...

result:

ok 300000 numbers

Test #36:

score: 0
Accepted
time: 243ms
memory: 31504kb

input:

50000 300000
2 67978 8834 607 845
2 55281 47225 610 531
3 4841 27009 27438 268 956 790
3 45567 57438 18161 881 520 156
5 65966 89900 55528 41734 75483 165 817 610 585 903
4 77129 3268 78932 6707 612 429 977 741
4 98598 9759 48996 67784 113 83 690 941
3 94790 19925 97890 864 469 144
4 68408 41314 413...

output:

30004.99308650161191103223
29361.43849500282783537841
28886.36820840018864586796
28370.96054546927552308944
29846.54890169417937251239
29031.13821302176041427856
28632.67028689844499922401
29009.34740933610321356184
29381.29260294840176825915
28503.44596840486501143630
29526.38185343940230787041
287...

result:

ok 300000 numbers

Test #37:

score: 0
Accepted
time: 249ms
memory: 31080kb

input:

50000 300000
4 42952 8648 61418 92401 722 553 118 627
3 12682 59383 2717 721 440 224
5 41053 80 39032 31216 11200 629 139 326 287 557
5 60670 24411 47997 22651 60438 964 105 517 469 9
5 24807 62977 74097 40262 9931 66 461 881 843 260
4 6284 71384 74529 27277 472 892 389 624
2 52888 18192 190 110
4 7...

output:

21741.37401291352242793664
22598.59791234857775954481
24732.62671643806328170001
23719.57355145838221233134
24885.67978300988653117543
20825.72698809795859276051
22828.34696439353920283111
26614.46650593597620471087
20824.53232655983320498194
24737.84960916166845734665
28427.51703063223273204585
238...

result:

ok 300000 numbers

Test #38:

score: 0
Accepted
time: 249ms
memory: 31024kb

input:

50000 300000
3 11664 16768 25764 650 496 851
5 75273 3863 90952 38022 93756 390 116 402 931 48
2 28002 6202 633 854
3 41009 16068 1948 33 109 276
4 7274 58076 51516 76811 516 69 815 947
4 50190 90273 20542 46285 316 227 465 421
4 28523 82839 94763 45130 114 557 209 471
5 23478 80816 66186 45147 2190...

output:

20152.55135940714863629353
4220.40198460915069711419
10665.43021381857081486544
5556.52128938924698786650
24563.71447987236874865857
23201.98648914570985368755
9083.80257200637717041047
7185.84670874904541282291
8114.79171441919007490284
12996.65327695824071074782
12377.76553912768549370327
23458.67...

result:

ok 300000 numbers

Test #39:

score: 0
Accepted
time: 207ms
memory: 32012kb

input:

50000 300000
5 78774 52771 81320 77251 20768 745 753 120 947 495
3 99639 23561 11087 711 167 561
4 73761 8225 37742 51836 948 330 430 292
3 38333 28403 34005 397 967 822
5 45857 53001 38335 59752 46496 154 558 732 612 178
3 72800 74792 29984 724 532 543
2 53692 64524 708 39
5 40222 37728 6479 61240 ...

output:

0.00000000000000000000
41.11000573473005286276
86.34967890796977323803
0.00000000000000000000
931.99404879890790664998
0.15528186924516006802
2893.44948559921214514823
0.00000000000000000000
0.14256966657929964954
0.00000000000000000000
0.00000000000000000000
13.33211195429500463792
0.00000000000000...

result:

ok 300000 numbers

Test #40:

score: 0
Accepted
time: 170ms
memory: 31236kb

input:

50000 300000
4 86894 17118 86760 54025 67 979 911 309
2 24133 37473 603 941
2 86734 93162 866 629
4 80658 1967 5972 76928 408 116 749 704
2 43089 94436 548 816
5 92816 50457 12911 40830 70667 5 34 838 86 566
2 58229 3378 883 952
4 2103 93145 22858 19481 33 791 547 949
3 85722 18733 93033 121 882 372...

output:

153.82863730232580025403
0.07027581885478281441
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.24916593131243849920
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000...

result:

ok 300000 numbers

Test #41:

score: 0
Accepted
time: 263ms
memory: 38480kb

input:

50000 300000
5 60519 1892 13772 11442 99197 193 926 519 101 185
5 10599 60099 40604 55719 37421 880 360 302 920 550
5 41018 42370 7479 42683 58623 748 535 233 193 352
5 4523 23932 47054 31686 9988 421 88 42 609 479
5 66085 42410 13711 5514 88439 597 752 476 173 939
5 58199 99182 54385 32201 19450 48...

output:

32010.86940295198149541989
32010.86876737540617021693
32010.86963006025446887293
32010.86786024287950880307
32010.86786024287950880307
32010.86854050033539742515
32010.86722583316072920923
32010.87081201406834551904
32010.86776958353968147719
32010.86899431181110742273
32010.86767893399583329028
320...

result:

ok 300000 numbers

Test #42:

score: 0
Accepted
time: 265ms
memory: 37972kb

input:

50000 300000
5 65688 27323 52741 32428 67898 393 463 913 518 485
5 54643 77541 56339 71054 1385 791 515 455 875 975
5 32271 79568 96171 58553 96949 193 965 835 567 915
5 93661 93677 46337 74228 58466 139 648 370 379 491
5 88280 79138 42561 92660 76447 977 821 879 464 169
5 48858 89306 7083 35632 521...

output:

32163.67812943986432827614
32164.85092633384912375050
32163.37927280534399621104
32164.83270904481763707849
32162.64040615748555040909
32164.68286366309568080624
32162.61459470998570964184
32164.17304156822124916459
32163.02909815189181763628
32163.33664665535769522364
32165.86571592457790735864
321...

result:

ok 300000 numbers

Test #43:

score: 0
Accepted
time: 246ms
memory: 38172kb

input:

50000 300000
5 97449 44094 45539 59427 79417 90 551 259 750 773
5 755 78461 70405 84188 25905 804 594 420 1000 161
5 15487 71214 84721 43369 69788 182 242 137 171 528
5 96976 58725 76324 90349 23380 463 131 186 292 508
5 44607 19030 60296 80580 53417 266 189 17 389 468
5 28209 72746 66070 95895 9710...

output:

32159.12006348299345503960
32087.72480480502417243827
32101.34891344194893747499
32078.90862519885103587569
32192.42396423993785070650
32089.56658678737640499889
32065.99598097965881571270
32106.87523203168954744058
32087.81433832345602219505
32142.12650542785244667243
32075.85902649586329538067
320...

result:

ok 300000 numbers

Test #44:

score: 0
Accepted
time: 264ms
memory: 38772kb

input:

50000 300000
5 61840 3702 21753 57513 53808 811 829 533 988 141
5 76213 50209 48660 11759 70331 677 259 105 149 908
5 55622 6254 10932 47176 52965 196 585 18 203 248
5 6366 80547 34345 69026 79347 185 337 816 854 654
5 82383 60870 4999 90067 74375 776 22 748 74 740
5 32613 59280 82942 50572 30460 48...

output:

31094.47124347258681709150
31676.31560669659771889428
31319.31366555660338057976
31331.53265730666120347792
31233.07918133582844433249
31870.06414531187270888779
31255.81999091643628041481
31823.36371216483561497057
31339.89991793172596601380
31537.03446509051821955438
31744.92905693943040290605
314...

result:

ok 300000 numbers

Test #45:

score: 0
Accepted
time: 269ms
memory: 38728kb

input:

50000 300000
5 14220 69596 48346 3650 3410 986 601 787 334 471
5 77482 92526 59347 8708 44918 75 47 545 481 82
5 39837 27060 69537 16208 54778 163 648 333 488 869
5 62025 12904 25149 55262 45704 946 436 588 309 248
5 84498 60957 80921 57550 98706 826 31 941 496 705
5 20161 31733 83228 16642 17798 24...

output:

28370.99455816628108806299
30728.18457414637032343308
25981.70974316979026852437
30338.74288675586473118528
27241.79133711687350327679
25804.37213932331438215328
31468.42679402219493844939
30479.61295601445852554434
28324.37230928941300689416
30145.57004595616129094537
30224.96823119848723315783
300...

result:

ok 300000 numbers

Test #46:

score: 0
Accepted
time: 259ms
memory: 38192kb

input:

50000 300000
5 49636 21618 70624 78040 90131 456 875 730 702 767
5 81935 70781 86918 53134 46791 36 732 695 636 548
5 7581 85975 73344 32089 57791 507 721 365 912 245
5 83847 46733 71122 11230 41721 856 577 853 455 912
5 36738 81468 14599 78508 18216 466 762 922 472 119
5 30887 15901 5202 74189 9406...

output:

10174.65601044390642559989
21773.94846662683133686755
9569.38967300075707544949
16887.22144263973732414286
9886.19274119722070004457
8607.09672697048536171849
30326.97128255255202944340
23983.06468508500151948226
28464.02639569591947577010
16794.54340502800895151836
11578.64239430981634981777
16263....

result:

ok 300000 numbers

Test #47:

score: 0
Accepted
time: 246ms
memory: 38232kb

input:

50000 300000
5 39723 72403 16760 60346 201 228 130 75 928 583
5 24252 81469 16571 27721 76189 632 684 27 106 297
5 95683 44581 42377 33902 48759 273 444 650 533 889
5 24716 61729 57359 77586 53890 955 349 12 345 574
5 69529 16174 25187 2839 53266 475 956 240 733 864
5 70636 91996 71272 61526 47535 9...

output:

5.70748960100519409696
3.36388542671009875573
246.59858822309880724277
750.95771741667235110729
6004.87335377782878254038
21686.37235656970724306802
19.67118162107814200237
7687.91718536252183779922
23.89801658464243274207
11.64544970016308369273
540.92911002673754855552
131.69803775585089772315
322...

result:

ok 300000 numbers

Test #48:

score: 0
Accepted
time: 190ms
memory: 38428kb

input:

50000 300000
5 91744 37786 66959 14364 83672 310 368 443 32 233
5 2507 9039 28293 29594 88150 21 833 774 277 728
5 54598 48388 58257 4211 61102 347 772 74 909 86
5 50032 74998 46030 73604 79097 584 911 751 713 351
5 46936 91068 70336 55054 64907 503 937 216 635 564
5 63316 70865 37331 37797 83977 94...

output:

6578.53446895210591849334
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
622.18741753907319552708
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
0.00000000000000000000
1790.32807839197272214982
0.00000000000000...

result:

ok 300000 numbers