QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#333431 | #6366. Message | CharlieVinnie | WA | 122ms | 12156kb | C++17 | 2.3kb | 2024-02-19 21:57:55 | 2024-02-19 21:57:57 |
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<=-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'