QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#188098#7231. Greedy gameucup-team004AC ✓24ms4828kbC++20833b2023-09-25 14:46:292023-09-25 14:46:29

Judging History

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

  • [2023-09-25 14:46:29]
  • 评测
  • 测评结果:AC
  • 用时:24ms
  • 内存:4828kb
  • [2023-09-25 14:46:29]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    
    std::vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        std::cin >> b[i];
    }
    
    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 0);
    std::sort(p.begin(), p.end(),
        [&](int i, int j) {
            return a[i] > a[j] || (a[i] == a[j] && b[i] > b[j]);
        });
    std::priority_queue<int> q;
    i64 ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        q.push(b[p[i]]);
        if (i % 2 == 1) {
            ans += q.top();
            q.pop();
        }
    }
    std::cout << ans << "\n";
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
1 2 3 4 5
2 3 4 5 6

output:

8

result:

ok single line: '8'

Test #2:

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

input:

10
1 1 1 1 1 1 1 1 1 1
2 3 9 5 6 6 1 2 3 4

output:

17

result:

ok single line: '17'

Test #3:

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

input:

15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

output:

7

result:

ok single line: '7'

Test #4:

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

input:

15
2 4 2 8 6 6 5 6 4 10 9 3 10 7 8
9 6 3 10 3 4 3 10 5 9 5 10 4 1 10

output:

60

result:

ok single line: '60'

Test #5:

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

input:

15
3 8 6 9 1 5 1 9 3 10 1 10 9 8 2
3 6 9 1 1 7 1 9 2 2 8 7 1 5 7

output:

47

result:

ok single line: '47'

Test #6:

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

input:

15
2 6 4 9 8 3 8 7 1 8 8 7 5 6 8
7 6 4 9 3 8 9 5 3 10 2 2 4 6 3

output:

46

result:

ok single line: '46'

Test #7:

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

input:

15
7 10 8 8 6 10 5 1 7 3 9 4 7 9 6
10 6 6 2 9 9 7 10 8 5 4 5 4 6 1

output:

56

result:

ok single line: '56'

Test #8:

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

input:

15
9 8 7 7 4 6 4 10 3 7 5 9 5 9 5
3 6 7 2 9 8 3 3 7 5 6 7 9 3 8

output:

55

result:

ok single line: '55'

Test #9:

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

input:

15
684567283 992849846 97315817 393416606 313535916 139886256 260942870 363653218 762787071 736738101 477119782 343012357 922635076 486445505 596119051
468386405 538725964 476297187 728411268 231052805 575996090 950540885 422247829 900469067 140007977 722808630 538320754 961487251 868922137 527102285

output:

5346487015

result:

ok single line: '5346487015'

Test #10:

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

input:

15
220108915 735849670 3920201 84584082 361456704 613923480 261729374 341005454 161747399 644675245 989698030 753835201 992061160 737318645 890863243
611087257 518109048 161952455 913550048 12692861 270850818 556403321 363405205 525666907 425754013 819193006 278676638 680329247 259507313 327149425

output:

4369763600

result:

ok single line: '4369763600'

Test #11:

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

input:

15
428748595 949568430 413698361 693373572 506459074 8655740 341958834 856964844 467830619 337893305 962962050 92077511 685503570 618863495 357957323
692050987 494543958 661075025 705370998 188177801 848190038 117298211 118839445 529533507 322237903 861794746 827783548 998221037 460251053 155829275

output:

5262225140

result:

ok single line: '5262225140'

Test #12:

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

input:

15
310486323 634006126 326650297 219785076 748543026 324083036 501631250 911531388 681036731 816392281 396911842 357739287 2962306 131080055 997401291
711277595 468030694 973664897 103874118 757507625 308013750 633225555 688550549 912068867 829459647 850613850 185641484 915162621 471153357 13141835

output:

5825473032

result:

ok single line: '5825473032'

Test #13:

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

input:

15
865322099 789162758 742776009 663818594 87708560 560205368 740746622 504705086 801365735 80172173 291547406 550820529 944437368 273968325 809195147
668767081 438569256 99722071 109059408 720682333 650321954 104185353 72538517 673272987 947419245 785650318 352250446 431153999 292214225 899087105

output:

5028684388

result:

ok single line: '5028684388'

Test #14:

score: 0
Accepted
time: 12ms
memory: 4652kb

input:

100000
1 5 7 1 6 8 1 7 9 2 7 7 6 1 8 6 5 1 8 1 9 6 3 9 7 7 4 6 10 9 9 8 6 9 8 10 10 5 10 2 2 8 6 6 6 6 1 8 3 8 3 8 2 5 6 4 9 8 3 6 8 7 7 8 10 10 2 10 5 3 5 7 9 10 8 2 4 9 4 4 9 6 3 4 1 2 1 9 10 9 9 10 10 8 7 5 10 6 8 5 2 3 5 9 9 8 5 9 4 4 3 10 9 5 8 8 7 10 1 5 10 6 2 1 1 3 3 10 1 1 7 6 5 10 2 9 7 9 ...

output:

387044

result:

ok single line: '387044'

Test #15:

score: 0
Accepted
time: 12ms
memory: 4736kb

input:

100000
10 6 1 4 1 8 5 4 8 10 5 8 7 5 10 4 4 8 10 9 10 10 3 4 1 5 2 3 4 8 9 6 8 2 5 6 3 6 1 9 8 6 4 2 7 7 1 4 6 5 3 7 2 4 9 5 8 10 9 6 6 10 3 10 2 10 4 6 8 4 4 1 3 6 7 4 8 10 5 6 8 2 5 9 3 10 4 9 10 6 2 8 8 8 5 8 3 9 6 4 9 1 9 10 7 1 2 3 2 9 2 9 10 3 4 9 2 5 6 5 7 5 1 5 6 4 3 3 9 6 2 6 9 6 5 10 3 3 5...

output:

388046

result:

ok single line: '388046'

Test #16:

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

input:

100000
6 1 1 6 7 8 10 6 7 6 8 7 6 5 3 2 4 4 8 10 10 3 2 3 10 3 8 6 7 8 4 3 2 7 4 4 5 7 8 5 4 10 3 6 4 1 4 7 5 6 9 5 8 9 4 4 9 4 2 4 4 3 8 2 3 8 5 10 2 3 9 7 9 3 1 5 5 3 9 7 4 4 5 3 4 2 5 1 5 7 10 5 6 6 7 7 2 1 5 9 6 1 8 9 2 6 1 6 6 3 9 9 9 5 5 10 8 3 6 7 7 4 5 3 7 8 9 10 2 6 5 10 8 7 8 6 5 10 8 5 5 ...

output:

387631

result:

ok single line: '387631'

Test #17:

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

input:

100000
9 2 5 7 5 8 5 3 4 10 5 6 10 2 8 9 3 8 2 6 9 6 8 6 6 10 2 5 7 8 4 9 8 6 4 4 4 9 10 10 8 2 3 9 7 9 2 8 1 10 4 3 1 10 1 10 4 10 3 1 4 7 3 5 3 4 4 1 6 10 8 6 7 3 2 6 5 9 5 6 7 2 3 6 4 7 6 4 3 1 10 3 3 1 2 3 5 1 7 1 4 3 4 6 4 2 1 6 6 4 5 10 7 2 2 1 4 3 3 10 9 4 4 5 6 5 3 2 10 1 6 10 3 2 2 7 6 1 5 ...

output:

387600

result:

ok single line: '387600'

Test #18:

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

input:

100000
8 7 4 7 3 6 2 6 1 2 7 5 1 5 5 6 3 10 3 5 6 8 3 2 7 7 4 10 6 8 8 4 6 6 6 6 2 10 8 4 2 1 3 1 5 10 4 7 4 9 5 10 2 6 9 4 1 8 2 7 5 2 9 7 1 7 2 10 10 5 3 6 7 5 10 7 7 7 4 4 6 6 9 9 4 6 6 9 6 9 4 2 10 3 2 7 4 9 1 9 4 7 4 10 3 10 1 3 3 3 9 2 3 3 4 3 2 6 6 5 3 4 9 2 2 6 2 7 2 1 6 5 5 1 6 5 3 6 6 1 4 ...

output:

387928

result:

ok single line: '387928'

Test #19:

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

input:

100000
329395763 605200206 806179577 598081996 161414986 311535116 843740930 374497508 572920491 153750761 333762002 185116767 697630586 375403855 299305931 117224435 199888974 938878457 880496718 770473145 236345510 985625675 476280469 192541667 480671767 266433770 335675764 107147941 231909277 816...

output:

37487670632088

result:

ok single line: '37487670632088'

Test #20:

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

input:

100000
595917875 55389390 744521721 465469612 180151594 992522700 638956994 737921284 43109739 914497065 453197970 870134271 7219930 932994095 317549003 642554067 149790318 759206745 132457198 490562041 756045158 141812651 560206485 604427107 873796343 824991786 163541908 816487877 724080093 9024198...

output:

37446270423724

result:

ok single line: '37446270423724'

Test #21:

score: 0
Accepted
time: 21ms
memory: 4748kb

input:

100000
535538035 976297510 186037641 250479242 295969784 594205320 513616014 639952214 420421879 460524285 33319710 482571241 940825600 121256045 508141963 106146577 96743488 393002335 991099848 604495821 158229298 253032081 458409365 394981307 877658773 329767166 800159078 124877607 26409473 174268...

output:

37452666193041

result:

ok single line: '37452666193041'

Test #22:

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

input:

100000
148256243 367924566 130727337 953110886 508869556 116582976 467717990 80590298 704856911 791832421 74127222 22427677 498447596 940189705 871084811 508001965 40748484 840265227 456424668 112274485 442897930 319283965 170889109 564204267 492259057 780759910 245527274 32317131 138897417 16106648...

output:

37441139110159

result:

ok single line: '37441139110159'

Test #23:

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

input:

100000
434072499 230270558 578590809 573364544 818850910 559655668 501262922 59835536 896414835 908421473 575620506 489703579 680085918 389795075 406377547 848120231 981805306 100995421 528431658 13898033 610051054 340568303 697645717 112095987 717597195 177970018 499646496 538806449 61543925 333338...

output:

37528719087054

result:

ok single line: '37528719087054'

Test #24:

score: 0
Accepted
time: 12ms
memory: 4820kb

input:

100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

output:

375239

result:

ok single line: '375239'

Test #25:

score: 0
Accepted
time: 13ms
memory: 4752kb

input:

100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

output:

37477679133533

result:

ok single line: '37477679133533'

Test #26:

score: 0
Accepted
time: 13ms
memory: 4748kb

input:

100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

output:

375514

result:

ok single line: '375514'

Test #27:

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

input:

100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

output:

37505905982098

result:

ok single line: '37505905982098'