QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#363118#8514. Joys of Tradingucup-team135#AC ✓26ms12436kbC++201.8kb2024-03-23 18:29:342024-03-23 18:29:34

Judging History

This is the latest submission verdict.

  • [2024-03-23 18:29:34]
  • Judged
  • Verdict: AC
  • Time: 26ms
  • Memory: 12436kb
  • [2024-03-23 18:29:34]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define app push_back
#define all(x) (x).begin(),(x).end()
#ifdef LOCAL
#define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl;}(#__VA_ARGS__, ":", __VA_ARGS__)
#else
#define debug(...)
#endif
#ifdef LOCAL
#define __int128 long long
#endif // LOCAL
#define y1 rtgerf
#define pt pair<double,double>
#define x first
#define y second
const double eps=1e-9;
pt operator+(pt a,pt b) {return pt(a.x+b.x,a.y+b.y);}
pt operator*(double c,pt a) {return pt(a.x*c,a.y*c);}
const int inf=1e18;
int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;cin>>n;
    double tot1=0,tot2=0;
    vector<pt> v;
    for(int i=0;i<n;++i)
    {
        int x,y,z,t;cin>>x>>y>>z>>t;tot1+=x*y;tot2+=z*t;
        double to=y+t;
        v.app({to*x,to*z});
    }
    sort(all(v),[&](pt o1,pt o2) {return o1.first*o2.second>o1.second*o2.first;});
    vector<pt> u;
    double s=0;for(auto h:v) {s+=h.first;}
    u.app({s,0});
    for(auto h:v)
    {
        pt o=u.back();o.x-=h.x;o.y+=h.y;u.app(o);
    }
    vector<pt> al=u;
    vector<pt> o=u;
    for(int i=0;i<o.size()-1;++i)
    {
        if(o[i].x>tot1 && o[i+1].x<tot1)
        {
            double c1=(tot1-o[i+1].x)/(o[i].x-o[i+1].x);double c2=(o[i].x-tot1)/(o[i].x-o[i+1].x);
            al.app(c1*o[i]+c2*o[i+1]);
        }
        if(o[i].y<tot2 && o[i+1].y>tot2)
        {
            double c1=(tot2-o[i+1].y)/(o[i].y-o[i+1].y);double c2=(o[i].y-tot2)/(o[i].y-o[i+1].y);
            al.app(c1*o[i]+c2*o[i+1]);
        }
    }
    double res=1e18;
    for(auto h:al)
    {
        if(h.x<=tot1+eps && h.y<=tot2+eps)
        {
            res=min(res,h.x+h.y);
        }
    }
    cout<<setprecision(25)<<res;
    return 0;
}

詳細信息

Test #1:

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

input:

2
1 2 4 1
2 1 3 4

output:

17.5

result:

ok found '17.500000000', expected '17.500000000', error '0.000000000'

Test #2:

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

input:

3
1 1 2 1
2 1 1 1
1 1 1 1

output:

6

result:

ok found '6.000000000', expected '6.000000000', error '0.000000000'

Test #3:

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

input:

72436
219 702 604 320
995 664 165 926
348 803 587 386
389 658 844 423
956 710 95 14
832 224 900 602
914 462 839 923
719 533 633 480
310 929 175 991
745 767 145 458
808 632 350 673
622 552 686 195
334 853 279 161
35 367 300 930
143 986 906 313
46 735 943 837
142 679 159 139
132 753 231 943
369 543 77...

output:

24132697873

result:

ok found '24132697873.000000000', expected '24132697873.000000000', error '0.000000000'

Test #4:

score: 0
Accepted
time: 23ms
memory: 10884kb

input:

97386
335 94 472 402
797 372 653 717
991 899 198 558
734 333 447 174
317 475 666 874
507 395 61 871
930 884 69 137
478 947 223 521
822 237 982 312
594 778 537 437
96 340 686 321
966 819 595 624
603 843 318 128
327 25 280 206
580 728 752 711
32 451 721 189
803 983 303 91
172 469 60 740
898 803 659 48...

output:

32628456306

result:

ok found '32628456306.000000000', expected '32628456306.000000000', error '0.000000000'

Test #5:

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

input:

73876
51 196 642 403
955 958 47 651
272 178 765 170
898 241 9 721
490 741 803 500
952 649 382 962
318 181 706 714
122 434 87 627
129 857 118 131
417 223 106 216
273 358 70 904
636 97 240 801
565 768 463 231
829 778 375 252
237 395 768 793
824 374 133 195
303 387 715 591
459 720 878 727
673 490 857 8...

output:

24625823256

result:

ok found '24625823256.000000000', expected '24625823256.000000000', error '0.000000000'

Test #6:

score: 0
Accepted
time: 22ms
memory: 11096kb

input:

100000
559 289 445 745
118 849 723 684
231 79 427 31
871 533 820 808
632 940 610 183
568 952 485 912
443 512 832 535
814 854 672 760
512 685 855 971
928 55 841 217
500 814 264 594
723 416 673 862
615 168 964 837
824 232 382 792
200 534 880 707
860 779 35 705
822 17 393 636
837 480 155 450
768 267 41...

output:

33553749432

result:

ok found '33553749432.000000000', expected '33553749432.000000000', error '0.000000000'

Test #7:

score: 0
Accepted
time: 23ms
memory: 11692kb

input:

100000
936 717 782 532
195 16 593 400
487 747 339 904
626 881 823 357
265 733 947 504
912 480 804 236
410 732 409 207
382 987 182 193
555 783 890 262
730 866 943 935
313 982 748 443
501 943 620 123
920 514 343 300
739 313 386 896
845 566 408 435
109 891 253 646
831 242 386 611
351 634 503 803
628 37...

output:

33466382073

result:

ok found '33466382073.000000000', expected '33466382073.000000000', error '0.000000000'

Test #8:

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

input:

7202
381 630 999 615
254 847 671 667
166 802 596 318
184 205 948 937
446 90 992 72
323 297 914 306
324 322 969 586
152 12 739 144
458 558 639 188
31 156 889 248
360 228 554 389
479 617 924 142
107 692 704 934
480 246 912 416
29 746 603 967
252 212 843 151
319 422 768 705
91 434 614 604
267 234 997 6...

output:

2433259526.666666507720947

result:

ok found '2433259526.666666508', expected '2433259526.666666508', error '0.000000000'

Test #9:

score: 0
Accepted
time: 3ms
memory: 4124kb

input:

9219
142 153 550 503
67 251 643 839
116 376 727 891
157 619 808 684
194 686 762 734
124 413 618 16
410 645 731 314
261 40 817 715
220 676 650 642
301 245 739 674
155 564 810 499
175 354 772 574
102 595 970 406
121 984 811 281
489 195 890 673
243 826 717 577
332 87 915 274
398 269 730 658
383 663 654...

output:

3100986076.713432788848877

result:

ok found '3100986076.713432789', expected '3100986076.713432789', error '0.000000000'

Test #10:

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

input:

2073
2 561 645 976
295 206 530 547
443 706 828 157
61 528 833 320
14 858 657 832
313 195 916 154
82 73 606 92
391 270 642 171
65 33 891 411
332 91 750 710
475 418 646 962
43 889 507 907
202 745 545 814
211 196 891 72
305 279 775 841
411 382 987 560
75 630 933 54
290 95 937 388
397 577 707 279
376 80...

output:

671885930.6659141778945923

result:

ok found '671885930.665914178', expected '671885930.665914178', error '0.000000000'

Test #11:

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

input:

2600
310 155 819 38
476 389 977 636
104 415 543 808
224 303 786 86
123 96 713 416
27 362 958 670
158 560 628 700
303 939 687 630
358 248 709 609
73 426 688 838
206 568 989 619
207 714 842 674
167 895 503 751
86 44 622 742
169 953 806 919
358 739 617 593
22 99 992 43
271 648 779 918
451 952 617 708
4...

output:

877097828.6458332538604736

result:

ok found '877097828.645833254', expected '877097828.645833373', error '0.000000000'

Test #12:

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

input:

4486
1 117 1000 977
1 240 1000 929
1 664 1000 821
1 156 1000 139
1 918 1000 658
1 795 1000 658
1 872 1000 466
1 553 1000 422
1 496 1000 131
1 435 1000 711
1 869 1000 160
1 267 1000 116
1 717 1000 878
1 894 1000 410
1 32 1000 926
1 979 1000 170
1 704 1000 973
1 583 1000 122
1 815 1000 189
1 890 1000 ...

output:

2201263461

result:

ok found '2201263461.000000000', expected '2201263461.000000000', error '0.000000000'

Test #13:

score: 0
Accepted
time: 26ms
memory: 10924kb

input:

100000
1 469 1000 850
1 642 1000 184
1 720 1000 558
1 19 1000 759
1 730 1000 425
1 251 1000 876
1 43 1000 365
1 850 1000 604
1 866 1000 814
1 883 1000 618
1 830 1000 683
1 279 1000 178
1 649 1000 914
1 667 1000 486
1 684 1000 539
1 612 1000 319
1 335 1000 561
1 699 1000 876
1 541 1000 279
1 191 1000...

output:

50249775489

result:

ok found '50249775489.000000000', expected '50249775489.000000000', error '0.000000000'

Test #14:

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

input:

5532
368 165 970 989
290 462 922 627
92 166 800 866
387 354 665 705
410 467 699 619
139 268 846 710
172 28 970 623
276 290 604 739
478 418 959 697
70 162 992 894
99 306 836 641
262 342 547 927
349 386 760 520
66 322 929 649
494 260 852 868
300 287 917 513
42 11 813 987
110 159 648 905
87 442 824 980...

output:

2386455996.181346893310547

result:

ok found '2386455996.181346893', expected '2386455996.181347370', error '0.000000000'

Test #15:

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

input:

7910
123 418 968 963
332 145 689 928
139 146 916 557
79 286 557 506
480 374 681 741
320 15 870 667
136 296 911 861
314 125 976 600
82 103 946 720
296 490 928 649
180 228 837 626
460 434 685 903
127 269 806 518
328 458 570 720
235 499 570 523
365 316 567 634
362 241 916 826
7 170 885 864
228 433 977 ...

output:

3406716361.814696788787842

result:

ok found '3406716361.814696789', expected '3406716361.814696312', error '0.000000000'

Test #16:

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

input:

100000
195 371 884 523
373 478 929 744
131 438 840 747
377 457 758 782
324 32 527 749
132 270 525 984
142 23 793 995
247 276 678 969
330 284 501 866
334 136 626 866
397 4 867 732
226 450 883 838
186 451 938 764
266 392 947 536
53 37 571 872
357 296 961 916
279 442 512 991
274 247 887 620
152 489 521...

output:

43093353479.00865936279297

result:

ok found '43093353479.008659363', expected '43093353479.008659363', error '0.000000000'

Test #17:

score: 0
Accepted
time: 16ms
memory: 11008kb

input:

100000
1 188 999 592
1 26 999 500
1 113 999 574
1 288 999 671
1 53 999 731
1 182 999 709
1 212 999 967
1 264 999 751
1 284 999 693
1 364 999 678
1 473 999 550
1 251 999 585
1 340 999 690
1 141 999 660
1 440 999 913
1 167 999 523
1 489 999 769
1 28 999 892
1 230 999 737
1 336 999 580
1 379 999 617
1 ...

output:

74979196897

result:

ok found '74979196897.000000000', expected '74979196897.000000000', error '0.000000000'

Test #18:

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

input:

4380
470 526 531 253
14 964 932 435
424 812 546 269
377 501 958 378
255 657 583 341
273 655 922 315
375 901 725 441
340 965 883 117
495 953 819 451
116 707 764 129
458 627 620 276
268 535 874 144
254 910 673 414
32 785 654 227
163 993 549 480
449 891 922 11
439 664 787 316
400 873 981 236
323 992 60...

output:

1222244675.71257495880127

result:

ok found '1222244675.712574959', expected '1222244675.712574959', error '0.000000000'

Test #19:

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

input:

2951
9 728 786 465
163 631 848 479
301 622 542 51
369 973 651 330
495 733 910 370
112 567 532 46
73 581 557 68
345 965 509 498
55 882 526 310
13 952 870 307
296 892 925 11
203 679 847 427
487 711 872 264
321 509 569 446
11 649 928 311
117 804 907 325
487 787 601 197
28 611 861 24
414 825 537 40
486 ...

output:

819594165.1000000238418579

result:

ok found '819594165.100000024', expected '819594165.100000024', error '0.000000000'

Test #20:

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

input:

67132
333 529 666 432
333 635 666 411
333 710 666 175
333 682 666 278
333 775 666 239
333 848 666 396
333 558 666 407
333 968 666 27
333 572 666 137
333 991 666 434
333 563 666 263
333 801 666 118
333 688 666 402
333 692 666 194
333 989 666 20
333 804 666 442
333 608 666 274
333 607 666 156
333 709 ...

output:

27916334388

result:

ok found '27916334388.000000000', expected '27916334388.000000000', error '0.000000000'

Test #21:

score: 0
Accepted
time: 17ms
memory: 9268kb

input:

76887
297 728 670 397
226 702 753 248
256 791 737 156
144 730 730 238
206 595 774 369
149 687 775 104
285 768 751 82
188 563 723 395
319 587 783 249
313 686 709 482
181 928 724 65
152 949 722 463
282 623 764 281
315 913 696 164
219 786 675 456
265 770 701 201
317 800 758 3
241 846 713 85
325 746 724...

output:

23192973484.16666412353516

result:

ok found '23192973484.166664124', expected '23192973484.166667938', error '0.000000000'

Test #22:

score: 0
Accepted
time: 18ms
memory: 8312kb

input:

66096
271 679 756 8
303 827 690 377
129 861 778 159
180 814 768 463
216 604 704 452
230 565 721 362
206 818 668 11
331 746 741 125
183 869 681 107
174 759 767 259
142 860 684 386
229 729 668 230
136 859 754 405
145 883 774 371
257 760 779 377
183 803 711 390
314 698 691 177
212 864 783 238
136 970 7...

output:

19926003385.66339874267578

result:

ok found '19926003385.663398743', expected '19926003385.663398743', error '0.000000000'

Test #23:

score: 0
Accepted
time: 23ms
memory: 10932kb

input:

100000
303 859 715 274
135 516 667 415
137 888 762 473
243 528 765 128
204 721 712 1
190 705 738 299
224 779 698 67
263 656 776 312
128 908 739 94
131 525 713 400
296 912 765 211
229 971 701 497
326 514 787 8
146 619 702 232
270 508 750 153
164 839 786 295
178 652 688 170
149 761 747 256
214 885 694...

output:

30194625176.50349426269531

result:

ok found '30194625176.503494263', expected '30194625176.503498077', error '0.000000000'

Test #24:

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

input:

3189
899 768 167 186
590 863 430 174
581 809 494 494
682 934 361 264
539 968 174 408
841 808 435 399
557 684 268 186
614 793 386 268
867 879 413 304
770 595 101 350
649 681 176 338
833 713 461 481
833 668 157 24
879 667 108 420
633 731 321 22
999 948 246 240
505 628 246 32
695 646 118 68
700 927 220...

output:

1367592773

result:

ok found '1367592773.000000000', expected '1367592773.000000000', error '0.000000000'

Test #25:

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

input:

8002
862 667 310 409
506 504 282 326
613 982 397 273
624 700 349 493
915 541 348 146
913 512 432 78
530 993 185 348
930 639 285 302
867 917 452 385
898 856 372 140
626 646 294 387
865 898 16 386
951 961 323 92
593 999 179 119
580 878 286 174
624 634 281 89
722 538 342 322
695 640 222 418
921 911 252...

output:

3430589426.480000495910645

result:

ok found '3430589426.480000496', expected '3430589426.480000019', error '0.000000000'

Test #26:

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

input:

5346
724 26 26 765
547 569 421 18
996 650 139 970
935 4 347 371
902 246 386 432
639 511 185 977
867 960 207 846
852 546 30 662
948 392 377 955
984 840 321 151
624 561 325 408
786 259 207 841
707 769 44 203
589 828 369 494
795 958 65 709
659 29 159 269
781 320 12 274
510 929 39 121
765 166 454 381
62...

output:

1801517425.54450249671936

result:

ok found '1801517425.544502497', expected '1801517425.544502735', error '0.000000000'

Test #27:

score: 0
Accepted
time: 3ms
memory: 4124kb

input:

9234
545 384 123 964
725 358 64 371
968 991 386 932
600 658 110 802
934 151 77 140
713 959 37 338
525 956 70 3
687 845 52 815
882 977 224 431
681 393 335 246
845 997 382 776
801 98 462 596
869 591 53 967
598 460 419 649
794 884 138 130
575 930 399 335
759 769 297 947
962 483 156 961
678 202 187 498
...

output:

3083530216.299107551574707

result:

ok found '3083530216.299107552', expected '3083530216.299107075', error '0.000000000'

Test #28:

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

input:

4016
520 491 449 685
563 301 159 723
688 45 239 535
822 461 250 974
601 237 197 666
954 472 419 607
650 311 411 616
662 359 126 753
763 316 219 720
609 341 226 758
933 21 408 523
585 390 494 776
858 318 104 702
940 98 299 803
540 373 293 750
985 387 240 918
662 89 368 612
646 373 357 661
625 215 406...

output:

1123080413.774193525314331

result:

ok found '1123080413.774193525', expected '1123080413.774193525', error '0.000000000'

Test #29:

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

input:

7685
504 174 87 916
902 415 181 1000
665 361 253 893
996 73 264 959
876 152 233 733
961 77 422 736
898 250 157 558
626 20 158 921
842 138 2 650
713 149 43 531
893 40 274 877
895 329 152 509
519 351 36 867
739 28 203 744
927 467 78 967
797 253 120 642
852 55 252 870
782 300 23 808
585 296 147 592
925...

output:

2116074111.135134935379028

result:

ok found '2116074111.135134935', expected '2116074111.135135174', error '0.000000000'

Test #30:

score: 0
Accepted
time: 10ms
memory: 7156kb

input:

49109
1000 285 1 921
1000 2 1 615
1000 329 1 848
1000 326 1 563
1000 297 1 851
1000 68 1 954
1000 455 1 775
1000 206 1 769
1000 52 1 867
1000 224 1 620
1000 23 1 736
1000 136 1 917
1000 359 1 922
1000 294 1 855
1000 31 1 925
1000 480 1 946
1000 355 1 845
1000 204 1 943
1000 24 1 633
1000 280 1 543
1...

output:

12305764977

result:

ok found '12305764977.000000000', expected '12305764977.000000000', error '0.000000000'

Test #31:

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

input:

10603
1000 661 1 467
1000 639 1 950
1000 692 1 515
1000 89 1 726
1000 168 1 299
1000 265 1 183
1000 414 1 100
1000 386 1 669
1000 681 1 942
1000 471 1 450
1000 216 1 586
1000 545 1 151
1000 663 1 7
1000 778 1 948
1000 381 1 196
1000 381 1 213
1000 995 1 67
1000 897 1 717
1000 493 1 824
1000 438 1 50...

output:

5369549522

result:

ok found '5369549522.000000000', expected '5369549522.000000000', error '0.000000000'

Extra Test:

score: 0
Extra Test Passed