QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#301329#6369. Frog JumpingSolitaryDream#WA 31ms8244kbC++171.3kb2024-01-09 17:58:492024-01-09 17:58:49

Judging History

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

  • [2024-01-09 17:58:49]
  • 评测
  • 测评结果:WA
  • 用时:31ms
  • 内存:8244kb
  • [2024-01-09 17:58:49]
  • 提交

answer

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

#define int long long

const int N=3e5+1e3+7;

int n,m,k,d,c[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>k>>d;
    for(int i=1;i<=m;i++)
        cin>>c[i];
    set<int> s;
    for(int i=1;i<=k;i++)
    {
        int x;
        cin>>x;
        s.insert(x);
    }
    sort(c+1,c+m+1);
    int ans=0;
    for(int i=m;i>1;i--)
    {
        int x=c[i];
        int p=1;
        vector<int> jmp;
        while(1)
        {
            if(p+d>=n)
                break;
            auto nxp=s.upper_bound(p+d);
            if(nxp==s.begin())
            {
                for(int j=i;j>1;j--)
                    ans+=c[j];
                for(auto x:jmp)
                    s.insert(x);
                break;
            }
            nxp--;
            if(*nxp<p)
            {
                for(int j=i;j>1;j--)
                    ans+=c[j];
                for(auto x:jmp)
                    s.insert(x);
                break;
            }
            p=*nxp;
            jmp.push_back(p);
            s.erase(nxp);
        }
    }
    int p=1;
    for(auto x:s)
    {
        if(p+d<x)
            ans+=c[1];
        p=x;
    }
    if(p+d<n)
        ans+=c[1];
    cout<<ans<<"\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

10 2 3 3
4 7
4 8 7

output:

4

result:

ok 1 number(s): "4"

Test #2:

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

input:

10 2 2 3
4 7
9 5

output:

15

result:

ok 1 number(s): "15"

Test #3:

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

input:

200000 1 1 3
218918215
92715

output:

437836430

result:

ok 1 number(s): "437836430"

Test #4:

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

input:

200000 1 1 782
106901742
116085

output:

213803484

result:

ok 1 number(s): "213803484"

Test #5:

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

input:

200000 1 1 99310
470724012
56740

output:

470724012

result:

ok 1 number(s): "470724012"

Test #6:

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

input:

200000 1 1 397388
866331561
81794

output:

0

result:

ok 1 number(s): "0"

Test #7:

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

input:

200000 1 1 366196424
320141515
2621

output:

0

result:

ok 1 number(s): "0"

Test #8:

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

input:

200000 1 10 5
557858482
147035 80127 3016 45003 198875 147608 95378 95913 55911 154570

output:

6136443302

result:

ok 1 number(s): "6136443302"

Test #9:

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

input:

200000 1 10 857
798079756
190803 44941 156382 20011 151186 30934 75614 171027 36421 12368

output:

8778877316

result:

ok 1 number(s): "8778877316"

Test #10:

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

input:

200000 1 10 77323
81465022
165863 8555 141636 162074 24267 190677 150729 52568 3435 122063

output:

0

result:

ok 1 number(s): "0"

Test #11:

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

input:

200000 1 10 6362589
436867804
129476 193807 73455 45400 113719 86285 22023 19582 193666 185427

output:

0

result:

ok 1 number(s): "0"

Test #12:

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

input:

200000 1 10 641765372
771571502
104484 34844 156779 15391 79618 157578 199281 9815 67278 80442

output:

0

result:

ok 1 number(s): "0"

Test #13:

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

input:

200000 1 100 6
780956883
97439 117410 28642 154629 183945 136830 615 155670 188072 122569 50885 118123 106428 114288 156877 18670 82340 22532 36195 153398 67859 148564 74493 109191 161147 187805 15868 140567 144296 177416 61346 82324 19043 5766 172232 66752 44509 24126 96571 131352 139304 141607 194...

output:

78876645183

result:

ok 1 number(s): "78876645183"

Test #14:

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

input:

200000 1 100 554
394386326
38334 179783 76256 194833 140409 35141 135372 4221 14666 43172 140515 141697 123871 65397 127212 83791 143458 12156 100382 7232 102868 99549 182087 55655 172518 31836 38813 41841 77378 55310 72049 71973 86801 80598 71070 174735 118643 173421 25741 38899 59002 49493 19893 1...

output:

29578974450

result:

ok 1 number(s): "29578974450"

Test #15:

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

input:

200000 1 100 83893
887295447
100706 128427 126706 151297 38720 60682 183920 20567 114775 132802 54873 159140 74980 45977 192332 64374 32055 76344 154215 42241 53853 17391 128550 67026 16548 54781 160577 195413 175762 66013 61699 59196 161634 70218 69838 48871 57693 11808 143533 168841 166886 183957 ...

output:

0

result:

ok 1 number(s): "0"

Test #16:

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

input:

200000 1 100 7160310
214850501
39104 88094 83169 49607 64260 109230 268 120676 4407 156376 181532 110249 45314 100852 172915 53998 106488 140422 189223 193224 171693 62825 139921 111054 39493 176544 93658 192769 186465 55663 48921 35059 151253 178202 53190 187920 106325 10138 73477 76727 111598 1893...

output:

0

result:

ok 1 number(s): "0"

Test #17:

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

input:

200000 1 100 419748069
514922935
89554 125094 160986 75148 112809 125576 110623 30800 38227 173819 132641 80584 110435 81435 71757 128432 150074 175431 129963 100820 27375 164978 183949 133999 60228 119872 101261 84010 176115 133667 14538 4186 59239 52338 83022 26307 114900 140080 171114 101975 1067...

output:

0

result:

ok 1 number(s): "0"

Test #18:

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

input:

200000 1 1000 1
326910705
161910 36782 76324 56495 164474 179171 95228 199779 56962 193319 46547 84978 114473 64900 71650 155761 191825 15526 63684 195229 130588 177851 1621 5026 6185 93899 91779 171182 119375 127770 93879 140893 70454 75525 114048 38494 146517 90575 40082 141263 29711 74092 75837 1...

output:

325929972885

result:

ok 1 number(s): "325929972885"

Test #19:

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

input:

200000 1 1000 568
445318823
38241 27467 178119 175362 182749 20539 169235 73109 64924 38834 117615 159988 53991 180167 74550 3524 136452 39645 142214 59715 132155 26678 88167 100691 68365 107747 160210 37412 48224 87843 120372 32603 156561 113196 42813 66499 195338 106685 45898 40581 191485 120439 1...

output:

26719129380

result:

ok 1 number(s): "26719129380"

Test #20:

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

input:

200000 1 1000 92199
457831690
148389 139508 96988 193637 24117 104791 52811 91317 110437 109902 182380 99507 179504 172822 112066 57368 59544 118175 6700 61282 90197 102978 173586 162871 92459 85396 135655 156012 117513 124582 22329 19740 194231 41960 161600 115320 11449 112501 134968 101327 37834 1...

output:

0

result:

ok 1 number(s): "0"

Test #21:

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

input:

200000 1 1000 2729258
961247784
140968 58377 115264 35005 108370 178119 60772 25556 191751 174667 121898 25022 172159 20585 176155 81487 39104 182659 8267 120352 57281 118107 46014 186965 70108 151623 64504 35550 34790 16292 9465 57410 122996 80212 119639 131430 7019 121035 195714 157920 64634 51904...

output:

0

result:

ok 1 number(s): "0"

Test #22:

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

input:

200000 1 1000 166145351
548478623
70083 76653 156629 119257 181698 186081 15504 197652 46272 114185 47413 17676 19922 74429 99247 160017 103588 184226 57091 196652 72410 71071 59862 164614 136335 80471 133794 51797 136745 3429 36889 186173 151001 129033 135748 137246 15554 72565 52309 184720 169297 ...

output:

0

result:

ok 1 number(s): "0"

Test #23:

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

input:

200000 1 10000 8
218184570
9441 62407 185950 31318 153697 193624 154986 22726 125989 104661 57286 55927 18098 81091 136270 1006 85639 44988 138025 110672 46123 190564 99878 60127 183129 98886 81253 138155 179648 46722 181719 96779 152526 159353 146660 65236 6144 58106 139369 66328 119617 121206 8144...

output:

1450054652220

result:

ok 1 number(s): "1450054652220"

Test #24:

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

input:

200000 1 10000 138
956181952
173083 147339 152943 174830 186957 80296 2428 41108 85482 49573 179346 53367 80428 44790 18766 107583 75132 113987 47411 175248 144867 124934 143269 77637 83598 97221 36401 87439 76392 185929 86504 124921 30145 55026 160336 115879 142377 16220 160716 39704 38601 126044 5...

output:

6693273664

result:

ok 1 number(s): "6693273664"

Test #25:

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

input:

200000 1 10000 89920
381038580
68262 114332 96457 8092 83874 127736 10563 101629 121177 171633 86005 125944 44127 117037 5880 97076 144131 33618 132479 84240 188454 67297 160778 178104 81933 52368 195929 184181 106383 80468 104400 93322 136061 159484 31473 72605 110737 146783 134092 148441 43439 103...

output:

0

result:

ok 1 number(s): "0"

Test #26:

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

input:

200000 1 10000 5936147
409631921
35256 138382 119471 94762 40533 146118 81330 46541 43239 78292 39119 79396 126620 114398 5619 166075 43270 108440 31225 18611 31847 185835 51002 176439 37080 11898 92673 3928 110138 108610 83047 188992 40521 30621 167706 30719 41301 10943 53076 153279 21272 102096 75...

output:

0

result:

ok 1 number(s): "0"

Test #27:

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

input:

200000 1 10000 909496785
13002623
59305 171642 26635 51420 149696 6640 26243 168601 149895 140622 101788 161889 113735 103891 74618 65214 128339 7186 165594 171218 140139 185274 49337 131587 196608 108640 122663 7683 18818 77011 178718 103698 111657 76072 125820 161282 105459 119679 57914 141358 194...

output:

0

result:

ok 1 number(s): "0"

Test #28:

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

input:

200000 1 100000 6
974149772
128811 110089 197031 110817 196037 179021 199095 833 176247 100323 24141 74218 148216 195862 63117 120738 169416 72477 70641 152909 65164 117692 5958 105163 89222 84015 2652 113234 150494 89501 40289 57409 22288 90923 118403 167244 72593 191368 40064 177226 52102 192153 3...

output:

1552794736568

result:

ok 1 number(s): "1552794736568"

Test #29:

score: 0
Accepted
time: 31ms
memory: 8240kb

input:

200000 1 100000 339
381494004
20767 49204 133472 17173 91818 124405 71317 101612 81144 16428 187391 193731 195199 171634 138497 90331 193404 46602 99894 4538 82241 20769 188304 183728 68727 138082 21726 58285 108925 34253 47134 85465 62742 26768 62346 192574 96133 26131 71615 62972 109548 198542 121...

output:

0

result:

ok 1 number(s): "0"

Test #30:

score: 0
Accepted
time: 27ms
memory: 8136kb

input:

200000 1 100000 91571
127435862
159880 94861 128551 92460 127984 105843 81314 97291 108523 88897 16125 30470 170971 36770 198872 124565 76747 75855 141274 11369 185316 13363 56626 163233 112548 27447 166774 26962 154705 41098 64944 35137 198586 61494 87676 115085 130893 148464 66577 29635 115937 756...

output:

0

result:

ok 1 number(s): "0"

Test #31:

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

input:

200000 1 100000 2333429
588411801
5538 89940 115114 138871 109421 196376 76993 23642 160500 8412 63108 6243 36107 107392 33108 88444 106000 117236 158351 114443 76883 81682 36131 7056 22405 172496 125206 171712 161550 69154 24862 170981 142530 86824 20434 50876 32737 143426 124023 116561 193002 6169...

output:

0

result:

ok 1 number(s): "0"

Test #32:

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

input:

200000 1 100000 793309368
63319545
91400 76503 50252 120309 199954 2303 94125 186892 80015 55395 119416 71377 106729 141626 106204 117697 147380 134313 61428 96792 35986 61187 90198 116911 157208 141173 80204 178557 98824 18826 160706 195461 167860 29828 145976 162963 37945 874 10950 3873 179088 160...

output:

0

result:

ok 1 number(s): "0"

Test #33:

score: -100
Wrong Answer
time: 0ms
memory: 3440kb

input:

200000 10 1 1
138846217 816505063 66917448 659164850 420923701 600771262 60874981 913244606 672279394 180151632
130818

output:

15824988984

result:

wrong answer 1st numbers differ - expected: '4590554135', found: '15824988984'