QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#750014	#7504. HearthStone	tarjen	AC ✓	942ms	61856kb	C++20	1.5kb	2024-11-15 12:06:22	2024-11-15 12:06:24

Judging History

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

[2024-11-15 12:06:24]
评测

测评结果：AC
用时：942ms
内存：61856kb

查看

[2024-11-15 12:06:22]
提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1e18;
void gmin(ll &x,ll y){
    if(y<x)x=y;
}
int pr[2000001];
ll sum[2000001],dp[2000001];
pair<int,int> all[2000001];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a.begin()+1,a.end());
    auto f =[&](int mid){
        int N=0;
        int j=1;
        for(int i=1;i<=mid;i++){
            while(j<=n&&a[j]<=i)all[++N]=make_pair(1,a[j]),j++;
            all[++N]=make_pair(-1,i);
        }
        while(j<=n)all[++N]=make_pair(1,a[j]),j++;
        memset(dp,0x3f,sizeof(dp));
        memset(pr,-1,sizeof(pr));
        memset(sum,0,sizeof(sum));
        dp[0]=0;
        int now=1000000;
        pr[now]=0;
        for(int i=1;i<=N;i++){
            sum[i]=sum[i-1]+(all[i].first==1?all[i].second:-all[i].second);
            now+=all[i].first;
            // cout<<"mid="<<mid<<" i="<<i<<" N="<<N<<" now="<<now<<endl;
            if(all[i].first==1)gmin(dp[i],dp[i-1]+max(0,all[i].second-mid));
            if(pr[now]!=-1)gmin(dp[i],dp[pr[now]]+abs(sum[i]-sum[pr[now]]));
            pr[now]=i;
        }
        // cout<<"mid="<<mid<<" ans="<<dp[N]<<endl;
        return dp[N];
    };
    int l=1,r=a.back();
    while (r-l>2) {
        int mid=(l+r)/2;
        if(f(mid) > f(mid+1)) l=mid; else r=mid+1;   //????
    } 
    ll ans=inf;
    for(int i=l;i<=r;i++)gmin(ans,f(i));
    cout<<ans<<"\n";
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 11ms

memory: 44756kb

input:

6
4 6 8 9 2 4

output:

result:

ok 1 number(s): "12"

Test #2:

score: 0

Accepted

time: 18ms

memory: 44872kb

input:

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

output:

result:

ok 1 number(s): "2"

Test #3:

score: 0

Accepted

time: 17ms

memory: 42724kb

input:

20
5 5 7 5 4 4 10 1 8 1 3 7 7 8 5 2 5 9 5 9

output:

result:

ok 1 number(s): "1"

Test #4:

score: 0

Accepted

time: 15ms

memory: 44888kb

input:

25
2 6 5 12 2 5 5 11 3 5 1 3 7 10 5 4 12 10 4 8 4 12 5 2 8

output:

result:

ok 1 number(s): "1"

Test #5:

score: 0

Accepted

time: 20ms

memory: 42764kb

input:

25
2 2 18 4 17 13 14 1 6 16 20 24 3 3 10 3 10 6 14 12 9 16 19 15 6

output:

result:

ok 1 number(s): "9"

Test #6:

score: 0

Accepted

time: 16ms

memory: 43916kb

input:

13
25 5 20 7 15 7 8 3 16 23 10 8 10

output:

result:

ok 1 number(s): "66"

Test #7:

score: 0

Accepted

time: 21ms

memory: 43184kb

input:

105
76 60 6 84 64 25 9 10 58 22 46 31 80 16 14 10 75 57 80 60 28 58 43 83 9 44 62 73 76 88 45 21 47 56 52 2 59 69 39 76 19 8 13 17 68 6 49 88 62 53 23 53 14 65 28 13 84 30 64 50 77 57 82 31 11 77 77 72 52 89 86 81 21 57 24 57 35 61 78 24 53 80 82 66 46 51 47 25 24 83 11 17 60 29 21 25 54 76 55 61 19...

output:

result:

ok 1 number(s): "129"

Test #8:

score: 0

Accepted

time: 28ms

memory: 44324kb

input:

500
17 5 59 21 20 16 59 8 41 79 50 72 51 45 20 45 46 86 76 28 14 22 11 82 8 23 37 16 75 29 71 52 50 89 54 8 33 65 27 31 47 59 39 13 43 6 55 68 41 78 28 56 44 55 45 46 48 54 50 5 29 52 87 87 71 33 64 6 2 35 27 39 72 48 20 69 48 23 22 87 31 26 44 80 5 22 3 82 67 39 29 58 56 81 68 12 49 30 49 68 86 69 ...

output:

result:

ok 1 number(s): "1"

Test #9:

score: 0

Accepted

time: 27ms

memory: 44536kb

input:

1000
9 81 55 45 54 13 14 32 88 21 39 13 100 20 14 81 72 30 53 66 73 37 59 43 3 1 20 60 60 15 14 45 13 77 17 34 9 4 21 39 79 43 84 89 35 71 55 93 72 20 66 11 60 64 94 65 71 5 17 49 84 11 42 24 6 66 3 89 22 53 97 14 66 36 59 29 54 99 81 25 92 35 18 74 93 13 80 30 18 89 31 38 32 65 97 41 52 77 48 95 97...

output:

result:

ok 1 number(s): "0"

Test #10:

score: 0

Accepted

time: 35ms

memory: 43088kb

input:

10000
184 50 415 13 913 24 597 640 706 688 37 927 774 169 714 941 894 926 323 545 585 650 52 839 391 809 596 153 522 119 199 170 247 492 93 541 323 792 835 753 673 579 344 256 171 24 698 480 63 11 570 401 524 297 725 896 84 447 412 147 885 126 439 38 355 493 526 654 664 168 440 276 583 503 799 381 3...

output:

result:

ok 1 number(s): "0"

Test #11:

score: 0

Accepted

time: 44ms

memory: 44512kb

input:

10000
4210 3733 4488 912 894 670 496 1222 727 3271 2853 4279 3277 1468 643 2574 2062 256 3969 135 605 4426 99 187 1143 4975 4225 4887 4162 4360 207 424 391 1637 3094 946 1001 3937 3699 2433 1038 4968 2374 527 3086 2967 2366 3887 2618 4964 1844 1089 2750 1469 1685 3808 1010 2205 3388 2328 2797 3852 2...

output:

result:

ok 1 number(s): "846"

Test #12:

score: 0

Accepted

time: 47ms

memory: 44272kb

input:

3000
9265 2616 8267 9004 4633 1888 7872 6994 1512 9826 339 5028 9190 612 2462 7409 9216 5805 7323 1838 8061 458 5975 3364 17 9134 6022 5061 5202 458 5687 9301 2842 2877 9593 6199 3181 2142 8238 2053 6940 680 2303 516 760 7237 1633 9303 1402 5438 8774 1170 8819 6066 3254 9378 255 8053 768 5740 5056 1...

output:

result:

ok 1 number(s): "9656961"

Test #13:

score: 0

Accepted

time: 58ms

memory: 44604kb

input:

4000
4295 6048 205 13966 1929 4461 13116 8417 14044 7261 4008 5424 6832 5689 10584 4612 6202 7792 1032 4184 12497 3714 37 10959 5372 359 6191 7270 6835 5083 9928 12924 2150 9973 5324 4279 6683 14201 1681 4992 2244 4234 12434 11466 6519 28 12998 13078 5864 11961 6198 3099 13428 490 6863 7501 10575 33...

output:

19583941

result:

ok 1 number(s): "19583941"

Test #14:

score: 0

Accepted

time: 934ms

memory: 61780kb

input:

1000000
80608 251073 980681 649495 561970 950614 76033 666468 116836 955978 87641 648542 279156 823327 256029 100512 154328 155177 452553 278682 409719 297297 280656 205454 605933 880725 153112 685012 442187 191814 152827 917527 560021 866825 332296 802518 781571 91031 177856 476452 98625 577021 352...

output:

174249444

result:

ok 1 number(s): "174249444"

Test #15:

score: 0

Accepted

time: 942ms

memory: 61856kb

input:

1000000
734923 276989 401041 865275 658138 885662 781455 862400 20539 147942 300911 468741 862949 278149 467363 84100 898146 814366 596848 826284 101267 758474 262831 450206 415081 565142 663885 250864 620205 598464 73611 135086 225914 630078 713599 804308 689469 866551 934034 851989 328700 534727 5...

output:

120543133

result:

ok 1 number(s): "120543133"

Test #16:

score: 0

Accepted

time: 937ms

memory: 61688kb

input:

1000000
171132 261498 584300 815166 377994 229007 359640 132393 892128 103801 807891 26464 435184 742580 511271 675591 383103 264749 70069 266488 412005 291334 734574 397566 29650 655318 897819 703256 824964 116839 462038 86141 475858 160758 451407 977618 864420 286582 276936 952053 40824 634958 758...

output:

128332022

result:

ok 1 number(s): "128332022"

Test #17:

score: 0

Accepted

time: 929ms

memory: 61852kb

input:

1000000
934499 904438 43275 2035 791405 314435 532360 791295 844656 26554 726881 799662 766547 692597 193615 49853 578112 124662 889997 835021 181222 345758 213789 629157 274232 700406 628932 438575 585964 451242 310857 49655 816956 653001 961787 635439 251496 577990 739752 578030 77042 455866 32093...

output:

170812168

result:

ok 1 number(s): "170812168"

Test #18:

score: 0

Accepted

time: 17ms

memory: 44472kb

input:

1000
8 5 16 1 17 20 12 2 5 3 20 11 11 19 8 3 19 18 11 1 9 20 8 3 7 4 16 8 11 7 18 15 2 20 18 14 2 3 19 8 5 17 1 3 4 17 4 10 17 19 11 12 6 20 9 12 3 11 8 3 20 3 5 17 1 2 5 20 19 7 7 4 2 1 3 13 2 15 12 16 12 10 7 2 11 9 19 19 12 8 11 12 17 17 3 18 8 6 7 1 13 2 2 18 3 4 16 5 3 2 17 16 19 19 8 6 5 13 17...

output:

result:

ok 1 number(s): "0"