QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#333431#6366. MessageCharlieVinnieWA 122ms12156kbC++172.3kb2024-02-19 21:57:552024-02-19 21:57:57

Judging History

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

  • [2024-02-19 21:57:57]
  • 评测
  • 测评结果:WA
  • 用时:122ms
  • 内存:12156kb
  • [2024-02-19 21:57:55]
  • 提交

answer

#include "bits/stdc++.h"
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](auto...){}(__VA_ARGS__)
#define debuga(...) [](auto...){}(__VA_ARGS__)
#endif
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
#define fi first
#define se second
using namespace std; typedef long long ll;
constexpr int N=2e5+5; using pii = pair<int,int>;
char a[N],b[N],s[N]; int n,m,pcnt,scnt,sp[N],nxt[N]; pii p[65]; ll c[N],sf[N],f[N],tmp[N];
signed main(){
    atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;});
    cin>>(a+1)>>(b+1); n=strlen(a+1); m=strlen(b+1); For(i,1,n) cin>>c[i];
    For(o,0,25){
        int x=-1; Rev(i,m,1) if(b[i]=='a'+o) x=i;;   if(x!=-1) p[++pcnt]=pii(x,o+1);
            x=-1; For(i,1,m) if(b[i]=='a'+o) x=i+1;; if(x!=-1) p[++pcnt]=pii(x,-o-1);
    }
    sort(p+1,p+1+pcnt); assert(p[1].fi==1&&p[pcnt].fi==m+1);
    debuga(p,1,pcnt);
    bool flg[26]={0};
    For(o,1,pcnt-1){
        if(p[o].se>0) flg[p[o].se-1]=1; else flg[-p[o].se-1]=0;
        if(p[o].fi==p[o+1].fi) continue;
        For(i,0,n) tmp[i]=-1e18;
        scnt=0; For(i,1,n) if(flg[a[i]-'a']) s[++scnt]=a[i],sp[scnt]=i,sf[scnt]=sf[scnt-1]+c[i];;; sp[scnt+1]=n+1;
        int L=p[o].fi,R=p[o+1].fi-1,K=R-L+1; nxt[L]=L-1;
        for(int i=L+1,j=L-1;i<=R;i++){
            while(j>L-1&&b[j+1]!=b[i]) j=nxt[j];
            if(b[j+1]==b[i]) j++;; nxt[i]=j;
        }
        for(int i=1,j=L-1;i<=scnt;i++){
            while(j>L-1&&b[j+1]!=s[i]) j=nxt[j];
            if(b[j+1]==s[i]) j++;
            if(j==R){
                j=nxt[j];
                ll res=-1e18; For(x,sp[i-K],sp[i-K+1]-1) res=max(res,f[x]);
                For(x,sp[i],sp[i+1]-1) tmp[x]=max(tmp[x],res+sf[i]-sf[i-K]);
            }
        }
        For(i,0,n) f[i]=tmp[i];
    }
    ll ans=-1e18; For(i,0,n) ans=max(ans,f[i]);
    debug(ans);
    if(ans<=-1e17) cout<<"You better start from scratch man...\n";
    else cout<<accumulate(c+1,c+1+n,0ll)-ans<<'\n';
    return 0;
}

// CONTINUE, NON-STOPPING, FOR CHARLIEY
// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING

// Started Coding On: February 19 Mon, 21 : 19 : 42

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

ababccb
abc
7 2 2 4 3 2 1

output:

7

result:

ok single line: '7'

Test #2:

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

input:

babab
baab
2 1 3 2 4

output:

You better start from scratch man...

result:

ok single line: 'You better start from scratch man...'

Test #3:

score: 0
Accepted
time: 62ms
memory: 12044kb

input:

bbaaaabbbbbabaababbaaabbbabaaaababaababaabababbbbabbbbababaabaaabbabaaaabbbabbaababababbabbbabbaababaaaaaabbabbbababbaabbbabbbabbbabaababaaaaaabaaababbbbbbaabaabaaaaaaabbbaaabaabbbababbbbbabbababaababaabbababbaababbbbbbbbbbbaabbbbbabaaabaabaaabaaaaabaaaabbbbbbbaaaabaabbbababbaaaabbabababbbabbbbabbab...

output:

You better start from scratch man...

result:

ok single line: 'You better start from scratch man...'

Test #4:

score: 0
Accepted
time: 71ms
memory: 12156kb

input:

bdabcfbdfcffebebcabbadacbbaeeaffbdedeedfabefdfdbddcecdaaddafdfbbdceccedebcecdfbcfbaafcefeecffdabfaacbeeecfeffaaafaefdcdaaeaeecfafcdadbfbccbdecacfeabdbfcacafebdcfbfbebacbffaecbfbcedccabbdecabaebbbdbcfbaeadfcadfadfaebaddbebfcbefdabdcefbbdaaaabcefedabcabcafedcfadedfdcbbccbffdcfdfcfcdfcfbbdabdbbeecafecc...

output:

You better start from scratch man...

result:

ok single line: 'You better start from scratch man...'

Test #5:

score: 0
Accepted
time: 114ms
memory: 12088kb

input:

soibsuydrizsuvymezuyrewmgwpnzxgyggpzjkdzooisgzbkfqjzkfcklluotqpwganvksoqtzixkfkrtqobdnregwgkxjwzsruvhztscxjyqlhfytomzhxiglxemdhkjnskrsqngojffogrkbygmdgzfwrlhwhhngqpjpepqgynsdybhpuaqhgjroijqofiwnxgxdmhofwsjnmwitruiesefzmabcfsyzrrruidewjowfkwwwqhztsmmtdnejlqhkmbpmknlxijnmzbtqviburbqwufipqsrqplcelovsxz...

output:

You better start from scratch man...

result:

ok single line: 'You better start from scratch man...'

Test #6:

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

input:

bbaaaabbbbbabaababbaaabbbabaaaababaababaabababbbbabbbbababaabaaabbabaaaabbbabbaababababbabbbabbaababaaaaaabbabbbababbaabbbabbbabbbabaababaaaaaabaaababbbbbbaabaabaaaaaaabbbaaabaabbbababbbbbabbababaababaabbababbaababbbbbbbbbbbaabbbbbabaaabaabaaabaaaaabaaaabbbbbbbaaaabaabbbababbaaaabbabababbbabbbbabbab...

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 91ms
memory: 12068kb

input:

hdhlkjabgckjkagfgkigfebfjmdabahajicgkfmblafmfgkiimkjlciiaegbkbkicgklhbhfmclghkleghmckbjliiicmmecldieghfdeghgechcjahdfebkhdigbkklcclieccijaemchbmfcggcjmgbdjhcbacleajjjledkfdjebgdmgahkjigjjighlbedbellabffeeckfbghcblmmgjijdehmcameeledejfijfmfcfkjdjklfldhmkabblcbgebhibkmihelehjccgggjhhbjehfidfmmjdgmmjbf...

output:

0

result:

ok single line: '0'

Test #8:

score: 0
Accepted
time: 122ms
memory: 12032kb

input:

soibsuydrizsuvymezuyrewmgwpnzxgyggpzjkdzooisgzbkfqjzkfcklluotqpwganvksoqtzixkfkrtqobdnregwgkxjwzsruvhztscxjyqlhfytomzhxiglxemdhkjnskrsqngojffogrkbygmdgzfwrlhwhhngqpjpepqgynsdybhpuaqhgjroijqofiwnxgxdmhofwsjnmwitruiesefzmabcfsyzrrruidewjowfkwwwqhztsmmtdnejlqhkmbpmknlxijnmzbtqviburbqwufipqsrqplcelovsxz...

output:

0

result:

ok single line: '0'

Test #9:

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

input:

aaaaaaaaaa
a
670064684 12247274 885150692 755303894 373857482 772871474 451986656 733926307 275101324 732261937

output:

4777621032

result:

ok single line: '4777621032'

Test #10:

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

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaa
807194254 763061330 636628022 447638039 310117480 873320507 134259988 666480259 747042520 231541618 643931761 30317274 158530414 253502390 229547045 438239031 709645547 367432988 755781758 67144518 360508870 862615691 635226301 863755466 104979114 4...

output:

5115514604

result:

ok single line: '5115514604'

Test #11:

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

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaa
768295104 305748099 281563038 518303412 678146171 512832379 509999474 360793781 979858190 884904151 886121576 776530718 147119220 985829130 553994391 500082956 167860347 562080893 520228135 790526162 270707017 179265550 913606870 245853815 83...

output:

21140461276

result:

ok single line: '21140461276'

Test #12:

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

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
684483834 637018127 270602950 736485564 883414052 758886073 266638494 906099301 851227039 479339928 603217972 474167559 537788182 324629484 719852776 8079...

output:

27302362948

result:

ok single line: '27302362948'

Test #13:

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

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

131859070652

result:

ok single line: '131859070652'

Test #14:

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

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

781196173176

result:

ok single line: '781196173176'

Test #15:

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

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

4343956108320

result:

ok single line: '4343956108320'

Test #16:

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

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

18494567762260

result:

ok single line: '18494567762260'

Test #17:

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

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

32209183658799

result:

ok single line: '32209183658799'

Test #18:

score: 0
Accepted
time: 39ms
memory: 9496kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

54681136007004

result:

ok single line: '54681136007004'

Test #19:

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

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

29370598770431

result:

ok single line: '29370598770431'

Test #20:

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

input:

aaaabababb
bb
476848657 19478030 860633182 479517749 926931997 990353030 811177212 276072809 44418816 639422667

output:

3786744940

result:

ok single line: '3786744940'

Test #21:

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

input:

baabbbaabbbbbbaaabbabababbbabb
aabbbbbbbbbbbb
596942736 513321407 582182914 466363879 661702687 696876564 738552457 374802663 475543850 315580035 306727219 980454952 485808481 677883937 518967937 895712736 991586358 554417767 795851770 921017576 109301858 423859119 202619045 804565823 583428190 4070...

output:

9486081373

result:

ok single line: '9486081373'

Test #22:

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

input:

bbaaaaababbaabbbabaaaaaaaaaaaaaaabaabaabbabbbbaaaa
bba
517088091 307183015 994179974 164146474 156595248 11692792 656694126 683962150 307132163 246359231 966105863 281059597 304728259 612665622 916423647 405320553 230841790 746930714 950416681 343242506 418374186 670629995 146835514 191417218 469803...

output:

21936514047

result:

wrong answer 1st lines differ - expected: '21735754192', found: '21936514047'