QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#185640#6401. Classic: N Real DNA PotsUESTC_Guest_WiFi#AC ✓849ms15680kbC++171.0kb2023-09-22 13:42:412023-09-22 13:42:42

Judging History

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

  • [2023-09-22 13:42:42]
  • 评测
  • 测评结果:AC
  • 用时:849ms
  • 内存:15680kb
  • [2023-09-22 13:42:41]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using db = long double;
using ll = long long;

const int N = 2e5 + 50;
using pll = pair<ll, ll>;
const db eps = 1e-15;

int n, k;
pll p[N];
db w[N];

bool check(db mid)
{
    for (int i = 1; i <= n; i++)
        w[i] = (p[i].second - mid * p[i].first) + (i * eps);

    set<long double> s;
    for (int i = 1; i <= n; i++)
    {
        auto x = w[i];
        if (!s.empty() && x < *s.rbegin())
            s.erase(s.lower_bound(x));
        s.insert(x);
    }
    return s.size() >= k;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> p[i].first >> p[i].second;

    db l = -3e9, r = 3e9;
    for (int cnt = 1; cnt <= 60; cnt++)
    {
        db mid = l + (r - l) / 2;
        if (check(mid))
        {
            l = mid;
        }
        else
            r = mid;
    }
    cout << fixed << setprecision(15) << l << "\n";
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5816kb

input:

4 3
1 2
2 4
3 3
4 1

output:

-1.000000004677815

result:

ok found '-1.0000000', expected '-1.0000000', error '0.0000000'

Test #2:

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

input:

2 2
1 1
5 3

output:

0.499999999736822

result:

ok found '0.5000000', expected '0.5000000', error '0.0000000'

Test #3:

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

input:

2 2
222640995 547139825
489207317 725361095

output:

0.668581341331520

result:

ok found '0.6685813', expected '0.6685813', error '0.0000000'

Test #4:

score: 0
Accepted
time: 4ms
memory: 5888kb

input:

1000 20
545612 774435015
828317 212155588
5294705 85926095
5648835 764528941
6159263 570820268
7177330 744079287
8446124 162286636
8735551 586528841
9263030 524140841
9505706 636254627
12111352 182639083
12750780 238494418
13149143 913232250
13382784 11485121
13699797 414697815
14263990 423817548
15...

output:

3.793210459276941

result:

ok found '3.7932105', expected '3.7932105', error '0.0000000'

Test #5:

score: 0
Accepted
time: 2ms
memory: 5764kb

input:

1000 100
163505 684865289
2674260 837752883
2694530 150054425
2870791 236723512
3262597 800933455
3558503 905056977
4260872 45990808
4532415 268478572
5299228 546172100
6019224 12074540
6345109 747272172
6539452 449655551
7215852 676269961
9062989 769545718
9444242 874911191
10264016 341805234
10595...

output:

-1.860577879264635

result:

ok found '-1.8605779', expected '-1.8605779', error '0.0000000'

Test #6:

score: 0
Accepted
time: 15ms
memory: 5776kb

input:

5000 10
34774 620025564
366562 278306777
446710 509672662
650220 70882120
824803 317731338
881144 257861254
1063458 61483347
1071840 639872836
1263842 30790337
1591940 346781076
1964777 814735151
2067497 63962255
2220071 379252135
2539054 428050443
2937092 423099578
3088992 959927412
3229098 9591796...

output:

134.621472802631814

result:

ok found '134.6214728', expected '134.6214728', error '0.0000000'

Test #7:

score: 0
Accepted
time: 19ms
memory: 5940kb

input:

5000 20
199760 355854017
326334 308841311
562097 142603502
737215 739382649
740379 538515503
775788 515038260
817583 280515397
919169 892864353
972326 662840403
1344912 46143677
1550928 380148689
1589971 740794446
1638208 835030507
1707737 1806402
1736374 716485086
1738772 965202367
1855327 28929729...

output:

19.107398866249903

result:

ok found '19.1073989', expected '19.1073989', error '0.0000000'

Test #8:

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

input:

100 80
3642237 433728851
3835922 596838254
4822541 903206579
11786229 71614574
28051109 568783761
37988181 991770771
56927147 913182266
80808317 468372188
96532943 867642142
97069884 869788913
104938691 736691068
115294599 927608069
130086679 135340679
143622561 267761236
147838354 653078316
1483162...

output:

-45.917501530212679

result:

ok found '-45.9175015', expected '-45.9175015', error '0.0000000'

Test #9:

score: 0
Accepted
time: 2ms
memory: 5700kb

input:

300 300
186421 261109479
5746147 454165382
9237830 637520496
9851923 811263876
11414218 355514230
13089969 488595547
14673543 646754325
16206307 26512314
20111827 236176303
29494991 773939650
31542488 394434870
33151870 729247973
35483496 458610267
39685298 553345644
41333867 843739706
41339284 5952...

output:

-45869.322134026516146

result:

ok found '-45869.3221340', expected '-45869.3221340', error '0.0000000'

Test #10:

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

input:

1000 2
747727 310492171
1468650 713980779
3789328 757125223
5320562 240087911
5661018 585322880
5727658 166258339
9628311 1509468
9663570 644887821
9705398 201079132
11009052 79093580
11528729 273302786
14435306 891929759
16986960 794877487
17773102 990984060
19350978 246181882
19465885 427225500
23...

output:

145656.485251215161981

result:

ok found '145656.4852512', expected '145656.4852501', error '0.0000000'

Test #11:

score: 0
Accepted
time: 53ms
memory: 6460kb

input:

10000 5000
11343 928311929
52379 840203434
261042 695151644
263788 172667944
364610 152184226
379806 619677738
515566 816745302
517646 466302942
540027 475750734
543982 124168292
640523 238869630
691715 468722215
705165 919447299
779673 129298873
1006841 948863833
1308410 643990798
1342527 5696458
1...

output:

-1045.873718458559254

result:

ok found '-1045.8737185', expected '-1045.8737185', error '0.0000000'

Test #12:

score: 0
Accepted
time: 64ms
memory: 8600kb

input:

10000 500
83515 736933811
214681 18821934
337773 255421593
373401 682078732
542837 930642686
743115 251178260
798454 390884216
1209834 124196728
1262528 560215146
1351188 9091629
1563890 525243183
1574212 997260354
1580426 699829078
1750092 395252098
1869757 67867660
1875112 226384476
2047018 328213...

output:

-5.629902788753527

result:

ok found '-5.6299028', expected '-5.6299028', error '0.0000000'

Test #13:

score: 0
Accepted
time: 60ms
memory: 6544kb

input:

10000 300
1639 469147828
114667 8224138
144408 364515807
212973 961202084
398743 285809740
496841 927819708
534650 867558923
686967 588702382
696690 666164443
726922 781870146
872473 615520296
898161 178383389
985406 97264277
996652 703675454
1254375 530922354
1573412 745036174
1637763 177874295
167...

output:

-1.304150532357995

result:

ok found '-1.3041505', expected '-1.3041505', error '0.0000000'

Test #14:

score: 0
Accepted
time: 66ms
memory: 6652kb

input:

10000 200
24361 355989436
67308 334706995
197996 808393732
208836 116843625
567811 484127866
694262 618656785
788342 790194385
849652 136657098
1029137 924171800
1203341 168259404
1211974 844956962
1214043 637541127
1420445 759167413
1655236 915436195
1657793 262449701
1691654 725474596
1767520 8976...

output:

-0.114468866677098

result:

ok found '-0.1144689', expected '-0.1144689', error '0.0000000'

Test #15:

score: 0
Accepted
time: 51ms
memory: 5884kb

input:

10000 100
448934 906394555
475014 997626342
590053 178642728
875628 903888948
1212211 346009502
1241514 309493863
1340826 712829848
1680222 758240743
1794126 477146449
1817597 186052442
1981543 779426336
2021852 433135353
2185476 494699476
2298672 422164227
2516850 625380828
2646484 337316798
267075...

output:

1.035376799921051

result:

ok found '1.0353768', expected '1.0353768', error '0.0000000'

Test #16:

score: 0
Accepted
time: 47ms
memory: 5888kb

input:

10000 50
40110 141597180
41162 930485122
87106 57859547
129179 279497823
217282 102811622
246011 688060074
527945 830469708
674775 425660310
781249 284422288
845105 393707471
1003702 918990189
1121790 534007402
1337016 917493002
1440969 636045451
1729947 231052670
1779758 199172396
1990895 270436931...

output:

5.115538362701622

result:

ok found '5.1155384', expected '5.1155384', error '0.0000000'

Test #17:

score: 0
Accepted
time: 35ms
memory: 7704kb

input:

10000 20
192005 992303174
386824 5538930
652843 617355627
665819 922060802
675553 291515142
791249 384248576
854934 231142457
926022 596717008
932239 945932944
969019 474307451
1374561 126586755
1567083 106513004
1629151 116861834
1670295 988693473
1775518 799130552
1792436 888344340
1820264 3853242...

output:

41.567725407587464

result:

ok found '41.5677254', expected '41.5677254', error '0.0000000'

Test #18:

score: 0
Accepted
time: 30ms
memory: 5868kb

input:

10000 10
266996 609205171
273102 735589575
277177 347655580
387543 606270266
469806 638663697
782692 72510150
796356 424656429
870781 260446185
926881 906882617
1343887 6609329
1382474 430796513
1550455 62337302
1552339 109538657
1629503 994097318
1808731 767302009
1877069 710955532
2206272 16406618...

output:

299.452481592604736

result:

ok found '299.4524816', expected '299.4524816', error '0.0000000'

Test #19:

score: 0
Accepted
time: 28ms
memory: 5840kb

input:

10000 8
88029 227530654
223658 46422449
264166 625625697
310448 286795635
454903 177457515
464676 839404426
687127 463087924
691931 190423638
704573 856226776
765895 482811447
768088 644745751
835500 427038249
919699 469313878
1032714 947023480
1152691 976821799
1197844 123594183
1286309 353740491
1...

output:

628.852979481231422

result:

ok found '628.8529795', expected '628.8529795', error '0.0000000'

Test #20:

score: 0
Accepted
time: 24ms
memory: 6032kb

input:

10000 5
62217 249235177
306503 34074294
477055 572914538
702905 839767773
704209 612222410
816080 392889606
861062 830566450
972418 999799224
1062852 573719854
1105278 478171882
1109703 803913526
1131824 820380955
1232243 740998431
1346238 6361814
1557725 497005895
1644920 318176224
1675339 14779790...

output:

3264.755751367087733

result:

ok found '3264.7557514', expected '3264.7557514', error '0.0000000'

Test #21:

score: 0
Accepted
time: 20ms
memory: 6016kb

input:

10000 2
81106 607376188
121099 653129920
571348 183766890
852412 97772619
885397 341954595
972399 314971005
1253363 493012266
1295891 104142101
1298100 659809152
1322651 842128537
1432357 889452372
1451236 918756370
1486954 86311912
1536631 770732857
1592430 17189991
1616977 439129337
1724413 646888...

output:

12931122.780820883399429

result:

ok found '12931122.7808209', expected '12931122.7792642', error '0.0000000'

Test #22:

score: 0
Accepted
time: 670ms
memory: 14980kb

input:

100000 50000
15057 358350989
39346 497842396
51813 37907067
52457 435919654
53100 875724585
58397 718257424
59957 37620444
67204 427984803
74005 329917739
74035 317952573
75181 793673458
79739 677360131
90807 331908646
102249 97003766
103081 951437983
105105 433577588
105745 722249067
111137 8229696...

output:

-10595.277870723354696

result:

ok found '-10595.2778707', expected '-10595.2778708', error '0.0000000'

Test #23:

score: 0
Accepted
time: 753ms
memory: 15536kb

input:

100000 20000
9323 677685425
14352 743079179
27428 611123223
37560 310598085
40204 780177048
63204 819646155
75150 47251013
77812 485531797
109722 432406359
129210 592704679
158564 802266075
160575 111024815
162290 140573044
173609 996619714
179478 899208368
181604 694506174
198759 146118416
201478 3...

output:

-1178.245545494643887

result:

ok found '-1178.2455455', expected '-1178.2455455', error '0.0000000'

Test #24:

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

input:

100000 10000
27122 784670388
52622 978773279
54369 605497801
56855 291806777
79140 185912169
82086 894702166
90642 526025925
112979 570953989
124993 350309338
125022 532367240
127941 2114724
128376 503025496
134023 126059042
171840 343298358
194986 822363413
231604 17376068
255216 203618065
266433 9...

output:

-273.851076102241131

result:

ok found '-273.8510761', expected '-273.8510761', error '0.0000000'

Test #25:

score: 0
Accepted
time: 801ms
memory: 14660kb

input:

100000 5000
1027 561371036
3497 339464673
13859 18712232
29827 576719761
48346 332534749
68143 55117324
84557 872658009
94409 77287019
97844 685493430
120163 586313701
129080 317911074
134194 538658651
142007 981246097
145948 144874419
150719 97107087
152074 956502946
154667 464585446
157050 6853228...

output:

-63.537542492955734

result:

ok found '-63.5375425', expected '-63.5375425', error '0.0000000'

Test #26:

score: 0
Accepted
time: 802ms
memory: 14576kb

input:

100000 2000
9586 395885811
19499 17791964
21501 515646844
24458 929922484
33438 843409039
42203 233776947
65186 34643920
67241 61748385
69684 74745975
69689 695199431
73734 539712050
83890 523922008
96539 362903030
105331 604030665
150789 315444612
152164 11492917
169636 963134733
173597 322648995
2...

output:

-9.278632050191415

result:

ok found '-9.2786321', expected '-9.2786320', error '0.0000000'

Test #27:

score: 0
Accepted
time: 849ms
memory: 15680kb

input:

100000 1000
37279 719439633
41236 899244998
56189 526653023
58056 75139811
58554 329362573
65892 575853640
80305 636046571
83360 262197963
89323 901720632
98393 821514157
106148 601081431
117128 683415607
131548 527010410
133103 976334293
135664 422372607
137700 675180489
160369 778400924
168358 761...

output:

-1.513711999495682

result:

ok found '-1.5137120', expected '-1.5137120', error '0.0000000'

Test #28:

score: 0
Accepted
time: 618ms
memory: 9364kb

input:

100000 500
4538 609062984
27394 664194059
36814 522659380
48139 213924960
57331 294361969
65363 289469759
67076 429417686
78659 225815816
82953 124914914
88572 765544043
92332 653764069
92570 871955651
103105 562686724
106835 196897094
108837 304680524
115090 163632601
117435 268917485
120664 986515...

output:

0.350194753404032

result:

ok found '0.3501948', expected '0.3501948', error '0.0000000'

Test #29:

score: 0
Accepted
time: 579ms
memory: 9328kb

input:

100000 200
443 494946847
1136 770256416
2156 934140327
7343 523000355
18728 796220105
26741 859625675
46654 498875298
57740 157205394
61173 371097343
83122 703098386
86169 201419625
93389 112241642
105861 70005244
114214 809057431
127649 458052547
127746 549557284
130105 451802967
153587 450484593
1...

output:

2.869230160754133

result:

ok found '2.8692302', expected '2.8692302', error '0.0000000'

Test #30:

score: 0
Accepted
time: 541ms
memory: 8800kb

input:

100000 100
742 769806192
22364 671452853
23549 147399779
33438 43219561
37309 79719025
39598 414948870
43654 437603809
43812 869926480
56359 252332126
60191 425624794
61153 895072308
68770 862835322
76937 90102582
86985 10375975
95094 521097568
110981 477684113
119551 215822109
119653 369297393
1278...

output:

11.883088929520724

result:

ok found '11.8830889', expected '11.8830889', error '0.0000000'

Test #31:

score: 0
Accepted
time: 483ms
memory: 8584kb

input:

100000 50
18095 571711091
21930 108862948
21971 110398625
32667 426759144
38284 61304179
38441 195533382
65389 181505118
75520 824130591
112301 760791192
115043 50058897
119641 752122266
125893 903793204
145748 502252425
149704 796285959
150470 737224515
151184 748841539
156347 501888906
173210 5613...

output:

56.062683719340645

result:

ok found '56.0626837', expected '56.0626837', error '0.0000000'

Test #32:

score: 0
Accepted
time: 385ms
memory: 9400kb

input:

100000 20
148 969161463
15604 20936932
35151 871342069
39144 995711018
62019 773917365
66807 930703509
103170 571336187
123167 653457542
132804 320784171
138555 548791949
141259 583332614
143425 143887708
145928 590550844
147466 680382534
167309 788372016
173134 236635431
178899 693842408
205921 230...

output:

556.465352671842162

result:

ok found '556.4653527', expected '556.4653527', error '0.0000000'

Test #33:

score: 0
Accepted
time: 285ms
memory: 9324kb

input:

100000 10
2579 41739412
38777 302086007
38893 181686988
39144 772068756
45775 563434514
47890 617943248
67246 864212263
69879 693953433
77239 883365651
92721 344866906
137348 524179754
150929 161340913
152918 968349467
153478 138993659
156019 154019001
172110 941042915
184532 282988828
187291 243864...

output:

6255.212858024758460

result:

ok found '6255.2128580', expected '6255.2128580', error '0.0000000'

Test #34:

score: 0
Accepted
time: 225ms
memory: 8364kb

input:

100000 5
2196 470379862
4797 779315854
25296 474566640
41665 273412567
48956 944514068
50716 93877934
62991 720794153
72463 207767146
74517 640968916
75327 155852615
102062 169668972
106425 666276651
117881 481112104
147595 116822347
148761 949175175
153541 735854794
158366 772849770
179305 59463703...

output:

65080.361296340413780

result:

ok found '65080.3612963', expected '65080.3612958', error '0.0000000'

Test #35:

score: 0
Accepted
time: 184ms
memory: 8976kb

input:

100000 2
5781 719080914
41847 712508921
59393 579625631
62824 395307537
64671 419094211
73114 371660748
88151 8811204
113375 946920145
114564 836434538
124363 481051724
132809 925100422
143689 177144359
149142 794585517
150451 85013520
158385 63005152
185672 126536934
201810 10990118
210355 10215188...

output:

435779477.985034975630697

result:

ok found '435779477.9850350', expected '435779499.3632069', error '0.0000000'

Test #36:

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

input:

98523 9234
3659 575662260
18358 324244108
22469 848523643
43733 430833319
54818 22575666
60692 90941061
79199 738214552
79411 809625199
81320 53481794
88103 894300843
88859 644555737
95236 353995031
99610 411357168
121324 478329707
138985 629767767
151141 561453566
154141 736312105
159062 853106015
...

output:

-230.285223603785005

result:

ok found '-230.2852236', expected '-230.2852236', error '0.0000000'

Test #37:

score: 0
Accepted
time: 461ms
memory: 8628kb

input:

84214 124
2260 634582757
9793 759881916
16577 277630207
63484 674289164
67040 865437585
70765 217708104
77649 642743520
83772 611666736
104103 334589224
105965 617232198
109575 436960890
154154 411646309
158899 239662764
160213 263166748
183186 755174143
191569 196536210
192104 496935097
194054 8841...

output:

5.979873424558080

result:

ok found '5.9798734', expected '5.9798734', error '0.0000000'

Test #38:

score: 0
Accepted
time: 710ms
memory: 14740kb

input:

87527 823
5821 189939949
11795 614465350
17041 897282310
20842 898368525
32736 355147835
47312 280001860
47435 596996879
61040 396091155
76215 384715093
78263 681244059
84160 915937692
87236 541770095
135110 323777852
139723 736024612
165350 875622051
173623 775689788
177725 692300315
182673 5960893...

output:

-1.013003670530255

result:

ok found '-1.0130037', expected '-1.0130037', error '0.0000000'

Test #39:

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

input:

3 2
114514 0
114515 1000000000
114516 0

output:

999999999.999996051890776

result:

ok found '999999999.9999961', expected '999999999.9912376', error '0.0000000'

Test #40:

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

input:

2 2
999999999 1000000000
1000000000 0

output:

-1000000000.031135746743530

result:

ok found '-1000000000.0311358', expected '-1000000000.0000000', error '0.0000000'