QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#258677 | #4568. Budget Distribution | LaStataleBlue | AC ✓ | 672ms | 108632kb | C++23 | 5.2kb | 2023-11-19 23:05:46 | 2023-11-19 23:05:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
void solve(){
int t,q;
cin>>t>>q;
const long double EPS = 1e-18, INF = 1e12, EPS2 = 1e-18;
vector<int> n(t),sump(t),sumc(t),currc(t);
long long tot=0;
vector<vector<int>> p(t),c(t);
long double currsumqb=0,currsumqf=0,currsumsqrtc=0;
vector<long double> val,sumsqrtc,sumqb,sumqf;
struct Update{
long double t;
int mode; // 0 = sqrtc upd, 1 = qb upd, 2 = qf upd
long double x;
};
vector<Update> tmp;
auto addqb = [&](long double l,long double r,long double val){
tmp.push_back({l,1,val});
tmp.push_back({r,1,-val});
};
auto addqf = [&](long double l,long double r,long double val){
tmp.push_back({l,2,val});
tmp.push_back({r,2,-val});
};
auto addsqrtc = [&](long double l,long double r,long double val){
tmp.push_back({l,0,val});
tmp.push_back({r,0,-val});
};
for(int i=0;i<t;i++){
cin>>n[i];
p[i].resize(n[i]);
c[i].resize(n[i]);
for(int j=0;j<n[i];j++){
cin>>c[i][j];
sumc[i]+=c[i][j];
}
tot+=sumc[i];
for(int j=0;j<n[i];j++){
cin>>p[i][j];
sump[i]+=p[i][j];
}
vector<pair<long double,int>> soglie;
long double qb=0,qf=0,qq=0;
for(int j=0;j<n[i];j++){
long double pp = (long double)(p[i][j])/sump[i];
long double cc = c[i][j];
if(sumc[i]-cc/pp<-EPS){
//cout<<"all'inizio "<<j<<" e' attivo\n";
soglie.push_back({cc/pp,j});
currc[i]+=c[i][j];
qf+=cc/sumc[i]-pp;
qq+=pp;
}
}
qb = sumc[i];
addqb(-INF,-currc[i]/(qb*qb),qb);
addqf(-INF,-currc[i]/(qb*qb),qf);
//cout<<"tra "<<-INF<<" e "<<-currc[i]/(qb*qb)<<" ho "<<qb<<" e "<<qf<<"\n";
soglie.push_back({qb,-1});
sort(soglie.begin(),soglie.end());
for(int j=1;j<soglie.size();j++){
addsqrtc(-currc[i]/(soglie[j-1].first*soglie[j-1].first),-currc[i]/(soglie[j].first*soglie[j].first),sqrt(currc[i]));
addqf(-currc[i]/(soglie[j-1].first*soglie[j-1].first),-currc[i]/(soglie[j].first*soglie[j].first),-qq);
//cout<<"tra "<<-currc[i]/(soglie[j-1].first*soglie[j-1].first)<<" e "<<-currc[i]/(soglie[j].first*soglie[j].first)<<" ho "<<sqrt(currc[i])<<" sqrt e "<<-qq<<"\n";
qb = soglie[j].first;
qf = 0;
for(int k=0;k<n[i];k++){
long double pp = (long double)(p[i][k])/sump[i];
long double cc = c[i][k];
if(k==soglie[j].second)qq-=pp;
if(qb-cc/pp<-EPS){
qf+=cc/qb-pp;
}
}
long double v1 = -currc[i]/(qb*qb);
currc[i]-=c[i][soglie[j].second];
long double v2 = -currc[i]/(qb*qb);
//cout<<"tra "<<v1<<" e "<<v2<<" ho "<<qb<<" e "<<qf<<"\n";
addqb(v1,v2,qb);
addqf(v1,v2,qf);
}
}
sort(tmp.begin(),tmp.end(),[](auto x,auto y){return x.t<y.t;});
for(int i=0;i<tmp.size();i++){
int ind = i;
auto t = tmp[i].t;
while(ind<tmp.size() && abs(tmp[ind].t-tmp[i].t)<EPS){
if(tmp[ind].mode==0){
currsumsqrtc+=tmp[ind].x;
}else if(tmp[ind].mode==1){
currsumqb+=tmp[ind].x;
}else{
currsumqf+=tmp[ind].x;
}
ind++;
}
//cout<<t<<" "<<currsumsqrtc<<" "<<currsumqb<<" "<<currsumqf<<"\n";
val.push_back(t);
sumsqrtc.push_back(currsumsqrtc);
sumqb.push_back(currsumqb);
sumqf.push_back(currsumqf);
i = ind-1;
}
for(int i=0;i<q;i++){
long long x;
cin>>x;
x+=tot;
int low = 0, up = val.size();
while(up-low>1){
int mid = (up+low)/2;
if(sumqb[mid]+sumsqrtc[mid]/sqrt(-val[mid])<=x){
low=mid;
}else{
up=mid;
}
}
//cout<<low<<" ecco\n";
if(low==val.size()-1){
cout<<"0.0\n";
}else{
long double llow = val[low], uup = val[low+1];
while(uup-llow>EPS2){
long double mid = (uup+llow)/2.0;
if(sumqb[low]+sumsqrtc[low]/sqrt(-mid)<=x){
llow=mid;
}else{
uup=mid;
}
}
cout<<setprecision(20)<<2.0*(sumqf[low]+sumsqrtc[low]*sqrt(-llow))<<"\n";
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3772kb
input:
1 5 3 1 7 10 700 400 100 0 2 10 50 102
output:
1.0555555555555555556 0.8666666666666667005 0.54761904761904770997 0.12745098039215692156 0
result:
ok 5 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
2 5 3 10 70 100 700 400 100 3 10 30 100 700 400 100 2 10 50 70 110
output:
2.2967032967032970387 2.2167763406551878925 1.8690167362600324001 1.7301587301587302696 1.5271317829457366121
result:
ok 5 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3844kb
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:
-1.626303258728256651e-19 -1.626303258728256651e-19 -1.626303258728256651e-19 -1.626303258728256651e-19 -1.626303258728256651e-19 -1.626303258728256651e-19 -1.626303258728256651e-19 -1.626303258728256651e-19 -1.626303258728256651e-19 -1.626303258728256651e-19
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 3936kb
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.4709264079809469517 4.4713875431599625801 4.4723107550016029384 4.4732866206182098408 4.4717464207319752049 4.4728241936468008714 4.4743668425990837552 4.4717464207319752049 4.472772832305171275 4.4740065777727856785
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 3764kb
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.603437800032037321 3.8023006558159549032 3.422887535368944501 2.9601681327193889585 2.920269830395813025 2.9004612230233661166 2.4984432884436078364 3.0732714917619668054 3.3676227919901688364 3.0541875978171226596
result:
ok 10 numbers
Test #6:
score: 0
Accepted
time: 0ms
memory: 4064kb
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:
1.084202172485504434e-19 0.2256255653317284631 1.084202172485504434e-19 1.084202172485504434e-19 1.084202172485504434e-19 1.084202172485504434e-19 1.084202172485504434e-19 1.084202172485504434e-19 1.084202172485504434e-19 1.084202172485504434e-19
result:
ok 10 numbers
Test #7:
score: 0
Accepted
time: 2ms
memory: 3860kb
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:
-1.8973538018496327595e-19 -1.8973538018496327595e-19 -1.8973538018496327595e-19 -1.8973538018496327595e-19 -1.8973538018496327595e-19 -1.8973538018496327595e-19 -1.8973538018496327595e-19 -1.8973538018496327595e-19 -1.8973538018496327595e-19 -1.8973538018496327595e-19 -1.8973538018496327595e-19 -1....
result:
ok 1000 numbers
Test #8:
score: 0
Accepted
time: 2ms
memory: 3892kb
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.1073985139291660645 6.1013526660634754438 6.1021862319639779762 6.1048205491700533848 6.1050779939721176717 6.1016731713386793659 6.1026354148136036709 6.1047562001614744248 6.1025712312672279435 6.1066887938264028781 6.103791549802216638 6.1010322819485544987 6.1057863697554911704 6.1048205491700...
result:
ok 1000 numbers
Test #9:
score: 0
Accepted
time: 2ms
memory: 3908kb
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.2531467048311009747 3.6245997204191144224 3.9731184747815700123 3.5401672701226589775 3.4811692961393850901 3.5230373411039485074 3.5678170256455157808 3.4329025052309411706 3.3273127304963515992 3.4555352460646823532 2.9746209884884121577 4.142132694413208369 4.0246625529969611386 3.1425881315149...
result:
ok 1000 numbers
Test #10:
score: 0
Accepted
time: 2ms
memory: 3848kb
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:
6.2341624917916504955e-19 6.2341624917916504955e-19 6.2341624917916504955e-19 6.2341624917916504955e-19 6.2341624917916504955e-19 6.2341624917916504955e-19 6.2341624917916504955e-19 6.2341624917916504955e-19 6.2341624917916504955e-19 6.2341624917916504955e-19 1.7796652036126104806 6.2341624917916504...
result:
ok 1000 numbers
Test #11:
score: 0
Accepted
time: 424ms
memory: 3848kb
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:
3.2187251995663412885e-19 3.2187251995663412885e-19 3.2187251995663412885e-19 3.2187251995663412885e-19 3.2187251995663412885e-19 3.2187251995663412885e-19 3.2187251995663412885e-19 3.2187251995663412885e-19 3.2187251995663412885e-19 3.2187251995663412885e-19 3.2187251995663412885e-19 3.218725199566...
result:
ok 300000 numbers
Test #12:
score: 0
Accepted
time: 342ms
memory: 3844kb
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.2303968092940446388 1.9114864909992347406 1.1775417793527668498 1.0293680220678281844 1.1188169685969761879 1.9014428880753017766 0.82354684178323681694 0.99064168222108664572 0.60706971982778092285 0.79928260037866930661 0.99580489108637991035 4.0575603916406708075 0.28456347418066699927 5.128153...
result:
ok 300000 numbers
Test #13:
score: 0
Accepted
time: 429ms
memory: 4084kb
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:
8.1315162936412832551e-19 8.1315162936412832551e-19 8.1315162936412832551e-19 8.1315162936412832551e-19 8.1315162936412832551e-19 8.1315162936412832551e-19 8.1315162936412832551e-19 8.1315162936412832551e-19 8.1315162936412832551e-19 8.1315162936412832551e-19 8.1315162936412832551e-19 8.131516293641...
result:
ok 300000 numbers
Test #14:
score: 0
Accepted
time: 1ms
memory: 3856kb
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:
1.4907779871675685968e-19 1.4907779871675685968e-19 1.4907779871675685968e-19 1.4907779871675685968e-19 1.4907779871675685968e-19 1.4907779871675685968e-19 1.4907779871675685968e-19 1.4907779871675685968e-19 1.4907779871675685968e-19 1.4907779871675685968e-19
result:
ok 10 numbers
Test #15:
score: 0
Accepted
time: 0ms
memory: 3792kb
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.6893450748109030387 6.6910320851607499983 6.6914543080158681394 6.690684513564316694 6.6894442274884336735 6.6915039936739413879 6.68998975306919567 6.6898905431989436352 6.6909079377966151365 6.6901385873825360679
result:
ok 10 numbers
Test #16:
score: 0
Accepted
time: 0ms
memory: 3904kb
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.0628597185136791172 3.6172011240476514967 3.4081429959024068797 3.3105246270289115547 4.594719658142069322 3.7752732887738884424 3.5790163621410461172 3.895206128086234411 3.3013735594906318241 3.3375166577448354417
result:
ok 10 numbers
Test #17:
score: 0
Accepted
time: 0ms
memory: 3788kb
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.0013595223172757484416 0.2093764700591211313 1.4378509954384477923 0.023374384151476639703 0.030492230606566469208 0.04851591018752726773 0.006165005466409412185 1.7728416650215677159 0.71794203530474187149 0.76041533876555017263
result:
ok 10 numbers
Test #18:
score: 0
Accepted
time: 0ms
memory: 4080kb
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:
-4.0149361699853836072e-19 -4.0149361699853836072e-19 -4.0149361699853836072e-19 -4.0149361699853836072e-19 -4.0149361699853836072e-19 -4.0149361699853836072e-19 -4.0149361699853836072e-19 -4.0149361699853836072e-19 -4.0149361699853836072e-19 -4.0149361699853836072e-19 -4.0149361699853836072e-19 -4....
result:
ok 1000 numbers
Test #19:
score: 0
Accepted
time: 2ms
memory: 3956kb
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.6721272450342555215 4.6728729781435236132 4.6723649263992951351 4.6728297249495815814 4.6728297249495815814 4.6728513512034842306 4.6728513512034842306 4.6724405696794107778 4.6725054134607654733 4.6721056417486004587 4.6721056417486004587 4.6729811231378794254 4.6725702634131418963 4.672840537990...
result:
ok 1000 numbers
Test #20:
score: 0
Accepted
time: 2ms
memory: 4100kb
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.8026046774862166562 5.3299286290859550809 5.0668435647076954416 5.7933129204692019668 5.0491655461644932789 5.6061866978625057665 5.3940568377749709872 5.4059942141139686557 5.2952577929146008653 5.0877993474083110376 5.0743464404839395019 4.8748748489167633867 5.0475070403188023304 5.271335366071...
result:
ok 1000 numbers
Test #21:
score: 0
Accepted
time: 2ms
memory: 4020kb
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:
-5.5565361339882102243e-19 -5.5565361339882102243e-19 -5.5565361339882102243e-19 -5.5565361339882102243e-19 0.38218936897698110855 0.0043534815388276311489 -5.5565361339882102243e-19 -5.5565361339882102243e-19 -5.5565361339882102243e-19 -5.5565361339882102243e-19 -5.5565361339882102243e-19 0.0452778...
result:
ok 1000 numbers
Test #22:
score: 0
Accepted
time: 425ms
memory: 3912kb
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:
4.0657581468206416275e-19 4.0657581468206416275e-19 4.0657581468206416275e-19 4.0657581468206416275e-19 4.0657581468206416275e-19 4.0657581468206416275e-19 4.0657581468206416275e-19 4.0657581468206416275e-19 4.0657581468206416275e-19 4.0657581468206416275e-19 4.0657581468206416275e-19 4.065758146820...
result:
ok 300000 numbers
Test #23:
score: 0
Accepted
time: 333ms
memory: 3868kb
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.886436986528908085 4.8284023249390471285 4.241524419983519598 2.0202661238945109055 2.0163013307453838403 2.336266636094382385 2.2778293143562615575 3.1152666545169217585 1.8297936261900145211 2.6638496068236532854 1.99675389392701844 2.3357840479697782286 1.8148518533163011637 1.85852025480565239...
result:
ok 300000 numbers
Test #24:
score: 0
Accepted
time: 360ms
memory: 4100kb
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.06989773071895644448 0.34796377176572835884 1.1740561642625933195 3.1509625637859972613e-19 0.095752085855227586834 2.6926153872299456653 0.026074512951665319143 0.75935775598226204074 3.1509625637859972613e-19 0.0022319034874975073344 0.062245652730629576725 0.034243873245603983227 0.554597245485...
result:
ok 300000 numbers
Test #25:
score: 0
Accepted
time: 461ms
memory: 5036kb
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.34352383840748058 600.34021325477776099 600.35920169440890387 600.338356250847483 600.34352383840748058 600.34809531135356059 600.3556248127405095 600.34228098010161201 600.35730634191557364 600.34352383840748058 600.35751674652672133 600.3458067555150573 600.34767878994073631 600.34166017668848...
result:
ok 300000 numbers
Test #26:
score: 0
Accepted
time: 451ms
memory: 4924kb
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.82994281015774879 589.94254593040176943 592.68007475301771453 589.904472426395179 590.02750815412711521 595.45012468273167255 592.6791403944098478 594.21691601574645025 591.33450906742966141 589.84846827146406983 592.84614973442412422 592.02807811556765183 592.64511142400937221 589.9327697432562...
result:
ok 300000 numbers
Test #27:
score: 0
Accepted
time: 427ms
memory: 4840kb
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.68090979183581168 559.88054278598644536 551.50105802642423636 485.14957706839149848 516.10130865301715042 504.08906983654132999 549.83378576331738469 589.05348203090684689 481.84203423925403642 530.36470167735941944 489.70304391168237873 515.25852626241871601 483.89213111053475119 549.4281202356...
result:
ok 300000 numbers
Test #28:
score: 0
Accepted
time: 406ms
memory: 4920kb
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.55518619087719057 404.78693509314136423 261.71174726438999697 408.27349855194813052 234.06815068484528342 344.01530113173362085 312.43287615017975067 172.18060386070899619 330.78424829769837565 164.60737996934833015 222.39138009942864316 238.43479866087184971 200.65568258548794467 220.8698100441...
result:
ok 300000 numbers
Test #29:
score: 0
Accepted
time: 375ms
memory: 4948kb
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.0467799972971831223 2.4915154941995161365 0.0996737265517146306 0.10047172689571225258 4.2057454902780470811 1.4913216449700380423 0.11280569084888884617 3.9058645881020581836 0.22683245032561191393 0.093696079355533608995 102.24300604223338407 0.044206317571231096311 0.035244587672474840107 0.471...
result:
ok 300000 numbers
Test #30:
score: 0
Accepted
time: 396ms
memory: 4948kb
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:
-8.4215403747811556912e-17 -8.4215403747811556912e-17 247.71522474392436693 -8.4215403747811556912e-17 -8.4215403747811556912e-17 -8.4215403747811556912e-17 -8.4215403747811556912e-17 -8.4215403747811556912e-17 -8.4215403747811556912e-17 -8.4215403747811556912e-17 0.0017785935926210506172 -8.4215403...
result:
ok 300000 numbers
Test #31:
score: 0
Accepted
time: 409ms
memory: 4868kb
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:
1.3757879706218769864e-16 1.3757879706218769864e-16 1.3757879706218769864e-16 1.3757879706218769864e-16 1.3757879706218769864e-16 1.3757879706218769864e-16 1.3757879706218769864e-16 1.3757879706218769864e-16 1.3757879706218769864e-16 1.3757879706218769864e-16 1.3757879706218769864e-16 1.375787970621...
result:
ok 300000 numbers
Test #32:
score: 0
Accepted
time: 397ms
memory: 5056kb
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:
-3.55721650594810479e-16 -3.55721650594810479e-16 -3.55721650594810479e-16 -3.55721650594810479e-16 -3.55721650594810479e-16 -3.55721650594810479e-16 -3.55721650594810479e-16 6.8831475479192921652 -3.55721650594810479e-16 -3.55721650594810479e-16 -3.55721650594810479e-16 -3.55721650594810479e-16 -3....
result:
ok 300000 numbers
Test #33:
score: 0
Accepted
time: 618ms
memory: 72236kb
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.11388086778399 30213.091549530067278 30213.100334037902856 30213.086943424481294 30213.121921136273745 30213.111060708954877 30213.126207822897904 30213.120971378196929 30213.126685416052943 30213.116237985133729 30213.092933685952131 30213.12764138168283 30213.091549530067278 30213.1300358516...
result:
ok 300000 numbers
Test #34:
score: 0
Accepted
time: 626ms
memory: 73404kb
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.20141254880658 30245.593030517207712 30253.281746210795751 30240.965322816305937 30247.256659050275251 30251.503209142676983 30252.303212136427772 30246.01980796842307 30254.961222288303997 30244.149119774388247 30249.204284587215371 30239.062360376050224 30256.253422822051094 30250.9051094121...
result:
ok 300000 numbers
Test #35:
score: 0
Accepted
time: 601ms
memory: 72248kb
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.180037957416996 30311.66780723775531 29963.739900854864818 30140.693205212456778 29961.927306547416721 30032.382537072711697 30238.868801641894494 30224.397394879062091 30203.918917766039215 30092.893952615171935 30142.871126613819561 29979.537871093839213 30341.559247789668897 30147.635897253...
result:
ok 300000 numbers
Test #36:
score: 0
Accepted
time: 597ms
memory: 72460kb
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.993086501636345 29361.438495002850289 28886.368208400207042 28370.960545469304815 29846.548901694201859 29031.138213021849882 28632.670286898482896 29009.347409336303866 29381.292602948447882 28503.445968405014391 29526.38185343948374 28781.279340311018299 29191.560542972409159 29789.240257951...
result:
ok 300000 numbers
Test #37:
score: 0
Accepted
time: 572ms
memory: 77348kb
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.374012915465212 22598.597912348651917 24732.626716439456281 23719.57355145839187 24885.679783010854511 20825.72698809867029 22828.346964395180256 26614.466505936416059 20824.532326562069143 24737.849609162175142 28427.517030632323486 23890.7089127398319 23944.659592500851796 26872.382905217103...
result:
ok 300000 numbers
Test #38:
score: 0
Accepted
time: 590ms
memory: 74580kb
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.551359407391692 4220.4019846158408003 10665.430213819656387 5556.521289393832431 24563.714479872674943 23201.986489146217552 9083.8025720099818736 7185.8467087545411074 8114.7917144202476121 12996.653276958934002 12377.765539129666166 23458.674158082834518 9904.9131080042294446 3369.5740628191...
result:
ok 300000 numbers
Test #39:
score: 0
Accepted
time: 557ms
memory: 76552kb
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:
9.8011347548623401695e-14 41.110005738844267297 86.349678909553867427 9.8011347548623401695e-14 931.99404880024961423 0.15528187022537378283 2893.4494856073301003 9.8011347548623401695e-14 0.14256967061068902519 9.8011347548623401695e-14 9.8011347548623401695e-14 13.332111955908645523 9.801134754862...
result:
ok 300000 numbers
Test #40:
score: 0
Accepted
time: 542ms
memory: 78168kb
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.82863730471056909 0.070275823723962856175 1.2165186201894025954e-13 1.2165186201894025954e-13 1.2165186201894025954e-13 1.2165186201894025954e-13 1.2165186201894025954e-13 0.2491659338117239919 1.2165186201894025954e-13 1.2165186201894025954e-13 1.2165186201894025954e-13 1.2165186201894025954e-1...
result:
ok 300000 numbers
Test #41:
score: 0
Accepted
time: 664ms
memory: 108064kb
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.869402951981403 32010.868767375406096 32010.869630060254394 32010.867860242879431 32010.867860242879431 32010.868540500335316 32010.867225833160655 32010.870812014068266 32010.867769583539603 32010.868994311811013 32010.867678933995768 32010.869130503104733 32010.871403614959275 32010.87113051...
result:
ok 300000 numbers
Test #42:
score: 0
Accepted
time: 672ms
memory: 108316kb
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.678129439864836 32164.850926333849383 32163.379272805344208 32164.832709044817797 32162.640406157486037 32164.682863663095802 32162.614594709986207 32164.173041568221542 32163.029098151892182 32163.336646655358026 32165.865715924577982 32165.201596045043008 32164.014317917788981 32165.29849260...
result:
ok 300000 numbers
Test #43:
score: 0
Accepted
time: 651ms
memory: 108632kb
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.120063483002198 32087.724804805102211 32101.348913441957112 32078.908625198866897 32192.423964239938377 32089.566586787392415 32065.995980979682054 32106.875232031719415 32087.814338323535521 32142.126505427853205 32075.859026495873673 32098.604279319796243 32089.427275250044543 32161.61160516...
result:
ok 300000 numbers
Test #44:
score: 0
Accepted
time: 670ms
memory: 107816kb
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.471243472752331 31676.315606696770789 31319.313665556632639 31331.532657307019779 31233.079181336018101 31870.06414531190396 31255.819990916736796 31823.363712164878752 31339.899917932163232 31537.034465090843476 31744.929056939568346 31436.189512930460072 31007.779908469228703 31294.306805809...
result:
ok 300000 numbers
Test #45:
score: 0
Accepted
time: 647ms
memory: 108108kb
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.994558169535544 30728.184574147265931 25981.709743173082133 30338.742886756111922 27241.79133711971946 25804.372139326056509 31468.426794022200109 30479.612956014709958 28324.372309290668516 30145.570045956380174 30224.968231198820959 30091.380003812266935 26469.828060171975867 31140.340308974...
result:
ok 300000 numbers
Test #46:
score: 0
Accepted
time: 666ms
memory: 107472kb
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.656010448726106 21773.94846663209592 9569.3896730084738671 16887.221442643355843 9886.1927412031575075 8607.0967269825247081 30326.971282553128518 23983.064685087003477 28464.026395697853173 16794.543405031833299 11578.642394312289738 16263.687070141899379 8221.0230567411878226 10751.346995425...
result:
ok 300000 numbers
Test #47:
score: 0
Accepted
time: 607ms
memory: 107468kb
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.7074896022728652755 3.3638854292773018063 246.59858822319241968 750.95771742925380449 6004.8733537854612998 21686.372356572496431 19.67118162375440297 7687.9171853688026332 23.89801659140070395 11.645449703626696993 540.92911003585114027 131.6980377738067276 322.83142243490432807 156.5954201548817...
result:
ok 300000 numbers
Test #48:
score: 0
Accepted
time: 420ms
memory: 108456kb
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.5344689549599857 0.0 0.0 0.0 0.0 0.0 622.18741754575788011 0.0 0.0 0.0 0.0 1790.3280783974681198 0.0 0.0 0.0 0.0 0.088642939995044774991 0.0 6.2430164082302589314 0.0 0.0 0.0 0.0 0.0 173.25981351091419524 0.0 328.74415088998098175 0.0 0.0 0.0 0.13642580167688075554 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0...
result:
ok 300000 numbers