QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#333430#6366. MessageCharlieVinnieWA 62ms12096kbC++172.3kb2024-02-19 21:56:272024-02-19 21:56:27

Judging History

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

  • [2024-02-19 21:56:27]
  • 评测
  • 测评结果:WA
  • 用时:62ms
  • 内存:12096kb
  • [2024-02-19 21:56:27]
  • 提交

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==-1e18) 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: 3732kb

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: 3792kb

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: -100
Wrong Answer
time: 62ms
memory: 12096kb

input:

bbaaaabbbbbabaababbaaabbbabaaaababaababaabababbbbabbbbababaabaaabbabaaaabbbabbaababababbabbbabbaababaaaaaabbabbbababbaabbbabbbabbbabaababaaaaaabaaababbbbbbaabaabaaaaaaabbbaaabaabbbababbbbbabbababaababaabbababbaababbbbbbbbbbbaabbbbbabaaabaabaaabaaaaabaaaabbbbbbbaaaabaabbbababbaaaabbabababbbabbbbabbab...

output:

1000099812223694318

result:

wrong answer 1st lines differ - expected: 'You better start from scratch man...', found: '1000099812223694318'