QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#333430 | #6366. Message | CharlieVinnie | WA | 62ms | 12096kb | C++17 | 2.3kb | 2024-02-19 21:56:27 | 2024-02-19 21:56:27 |
Judging History
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'