QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#393215#6366. MessageCharlieVinnieRE 268ms31508kbC++176.7kb2024-04-18 12:05:042024-04-18 12:05:05

Judging History

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

  • [2024-04-18 12:05:05]
  • 评测
  • 测评结果:RE
  • 用时:268ms
  • 内存:31508kb
  • [2024-04-18 12:05:04]
  • 提交

answer

#include "bits/stdc++.h"
#undef DEBUG
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](){}()
#define debuga(...) [](){}()
#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)
using namespace std; typedef long long ll;
constexpr int N=2e5+5;
char S[N],T[N],a[N],b[N]; int n,m,acnt,bcnt,posa[N],nxt[N],to[N][30],Xsum[N],Ysum[N],Xpos[N],Ypos[N],vis[26],V,cmp[30][30]; ll w[N];
int ban[N],beg[N]; ll val[N],f[N],tmp[N];
inline void ckmin(int& x,int y) { x=min(x,y); }
inline void ckmax(int& x,int y) { x=max(x,y); }
signed main(){
    atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;});
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>(S+1)>>(T+1); n=strlen(S+1); m=strlen(T+1); For(i,1,n) cin>>w[i];
    if(n<m) return cout<<"You better start from scratch man...\n",0;
    For(i,1,m) if(!vis[T[i]-'a']) vis[T[i]-'a']=++V;
    debug(vis);
    For(x,0,25) if(vis[x]) For(y,x+1,25) if(vis[y]) {
        acnt=bcnt=0;
        For(i,1,n) if(S[i]=='a'+x||S[i]=='a'+y) a[++acnt]=S[i],posa[acnt]=i;
        For(i,1,m) if(T[i]=='a'+x||T[i]=='a'+y) b[++bcnt]=T[i];
        int Xcnt=0,Ycnt=0;
        For(i,1,acnt){
            if(a[i]=='a'+x){
                Xpos[Xsum[i]=++Xcnt]=i; Ysum[i]=Ycnt;
            }
            else{
                Ypos[Ysum[i]=++Ycnt]=i; Xsum[i]=Xcnt;
            }
        }
        int L=1; while(b[L+1]==b[L]) L++;
        int R=bcnt; while(b[R-1]==b[R]) R--;
        L++; R--;
        if(L>R){
            int u=(b[1]=='a'+x?x:y);
            int v=(b[bcnt]=='a'+x?x:y);
            assert(u!=v);
            cmp[vis[u]][vis[v]]=1;
            cmp[vis[v]][vis[u]]=-1;
            For(i,1,acnt){
                if(a[i]=='a'+v){
                    if(v==y){
                        if(Ysum[i]<bcnt-R) continue;
                        int t=Ypos[Ysum[i]-(bcnt-R)+1];
                        if(Xsum[t-1]<R) continue;
                        int o=Xpos[Xsum[t-1]];
                        to[posa[i]][vis[x]]=posa[o];
                    }
                    else{
                        if(Xsum[i]<bcnt-R) continue;
                        int t=Xpos[Xsum[i]-(bcnt-R)+1];
                        if(Ysum[t-1]<R) continue;
                        int o=Ypos[Ysum[t-1]];
                        to[posa[i]][vis[y]]=posa[o];
                    }
                }
            }
            continue;
        }
        bool oth=0; For(i,L,R) if(b[i]!=b[L]) { oth=1; break; }
        if(!oth){
            if(b[L]=='a'+x){
                cmp[vis[y]][vis[x]]=-1;
            }
            else{
                cmp[vis[x]][vis[y]]=-1;
            }
        }
        nxt[L]=L-1;
        for(int i=L+1,j=L-1;i<=R;i++){
            while(j>=L&&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<=acnt;i++){
            while(j>=L&&b[j+1]!=a[i]) j=nxt[j];
            if(b[j+1]==a[i]) j++;
            if(j==R){
                j=nxt[j];
                if(a[i]=='a'+x){
                    if( (b[1]=='a'+x?Xsum[i-(R-L+1)]:Ysum[i-(R-L+1)])>=L-1 && Ysum[acnt]-Ysum[i]>=bcnt-R ){
                        int u = Ypos[Ysum[i]+(bcnt-R)]; to[posa[u]][vis[x]]=posa[i]; to[posa[i]][vis[y]]=posa[u];
                    }
                }
                else{
                    if( (b[1]=='a'+x?Xsum[i-(R-L+1)]:Ysum[i-(R-L+1)])>=L-1 && Xsum[acnt]-Xsum[i]>=bcnt-R ){
                        int u = Xpos[Xsum[i]+(bcnt-R)]; to[posa[u]][vis[y]]=posa[i]; to[posa[i]][vis[x]]=posa[u];
                    }
                }
            }
        }
    }
    // For(u,1,V){
    //     int lst=0;
    //     For(i,1,n) if(vis[S[i]-'a']==u) {
    //         if(lst==0) { lst=i; continue; }
    //         For(v,1,V) if(cmp[u][v]==1) to[i][v]=max(to[i][v],to[lst][v]);
    //         lst=i;
    //     }
    //     lst=0;
    //     Rev(i,n,1) if(vis[S[i]-'a']==u) {
    //         if(lst==0) { lst=i; continue; }
    //         For(v,1,V) if(cmp[u][v]==-1) to[i][v]=min(to[i][v],to[lst][v]);
    //         lst=i;
    //     }
    // }
    For(i,1,V) debuga(cmp[i],1,V);
    For(u,1,n){
        For(i,1,V) if(vis[S[u]-'a']!=i) debug(u,i,to[u][i]);
    }
    For(x,1,V){
        int L=0,R=0;
        For(i,1,m) if(vis[T[i]-'a']==x) R=i;
        Rev(i,m,1) if(vis[T[i]-'a']==x) L=i;
        For(i,L,R-1) ban[i]=1;
        int cntB=0; For(i,1,m) if(vis[T[i]-'a']==x) cntB++;
        static int pos[N]; int pcnt=0; ll qwq=0;
        For(i,1,n) if(vis[S[i]-'a']==x){
            qwq+=w[i]; pos[++pcnt]=i;
            if(pcnt>=cntB) qwq-=w[pos[pcnt-cntB]],val[i]=qwq,beg[i]=pos[pcnt-cntB+1];
            else val[i]=-1e18;
        }
    }
    debuga(val,1,n);
    f[0]=0; For(i,1,n) f[i]=-1e18;
    int has[30]={0};
    auto work=[&](){
        For(i,0,n) tmp[i]=f[i],f[i]=-1e18;
        For(i,1,n) tmp[i]=max(tmp[i],tmp[i-1]);
        int qwq=0;
        For(u,1,V) if(has[u]){
            int ok=1;
            For(v,1,V) if(has[v]&&cmp[u][v]!=0) { ok=0; break; }
            if(ok) { qwq=u; break; }
        }
        debug(qwq);
        assert(qwq);
        For(i,1,n) if(vis[S[i]-'a']==qwq) {
            int pos[30]={0};
            function<bool(int,int)> dfs=[&](int u,int o){
                if(pos[u]) return pos[u]==o?true:false;
                else pos[u]=o;
                For(v,1,V) if(v!=u&&cmp[u][v]==0){
                    if(to[o][v]==0) return false;
                    if(!dfs(v,to[o][v])) return false;
                }
                return true;
            };
            if(!dfs(qwq,i)) continue;
            For(u,1,V) if(has[u]) assert(pos[u]);
            int OK=1; For(u,1,V) if(has[u]) For(v,1,V) if(has[v]){
                if(cmp[u][v]==1&&pos[u]>to[pos[v]][u]) { OK=0; goto OUT; }
            }
            OUT: if(!OK) continue;
            int mx=0,mn=1e9; For(u,1,V) if(has[u]) mx=max(mx,pos[u]),mn=min(mn,beg[pos[u]]);
            if(mn==0) continue;
            ll tt=0; For(u,1,V) { tt+=val[pos[u]]; if(tt<-1e18) break; }
            f[mx]=max(f[mx],tmp[mn-1]+tt);
        }
    };
    debuga(ban,1,m);
    For(i,1,m){
        has[vis[T[i]-'a']]=1;
        if(!ban[i]){
            work(); memset(has,0,sizeof(has));
            debug(i); debuga(f,0,n);
        }
    }
    ll ans=-1e18; For(i,1,n) ans=max(ans,f[i]);
    if(ans<0) cout<<"You better start from scratch man...\n";
    else{
        ans=-ans; For(i,1,n) ans+=w[i];
        cout<<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: April 18 Thu, 07 : 48 : 39

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

ababccb
abc
7 2 2 4 3 2 1

output:

7

result:

ok single line: '7'

Test #2:

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

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: 25ms
memory: 15800kb

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: 56ms
memory: 12960kb

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: 268ms
memory: 11540kb

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: 17ms
memory: 15864kb

input:

bbaaaabbbbbabaababbaaabbbabaaaababaababaabababbbbabbbbababaabaaabbabaaaabbbabbaababababbabbbabbaababaaaaaabbabbbababbaabbbabbbabbbabaababaaaaaabaaababbbbbbaabaabaaaaaaabbbaaabaabbbababbbbbabbababaababaabbababbaababbbbbbbbbbbaabbbbbabaaabaabaaabaaaaabaaaabbbbbbbaaaabaabbbababbaaaabbabababbbabbbbabbab...

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 110ms
memory: 12128kb

input:

hdhlkjabgckjkagfgkigfebfjmdabahajicgkfmblafmfgkiimkjlciiaegbkbkicgklhbhfmclghkleghmckbjliiicmmecldieghfdeghgechcjahdfebkhdigbkklcclieccijaemchbmfcggcjmgbdjhcbacleajjjledkfdjebgdmgahkjigjjighlbedbellabffeeckfbghcblmmgjijdehmcameeledejfijfmfcfkjdjklfldhmkabblcbgebhibkmihelehjccgggjhhbjehfidfmmjdgmmjbf...

output:

0

result:

ok single line: '0'

Test #8:

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

input:

soibsuydrizsuvymezuyrewmgwpnzxgyggpzjkdzooisgzbkfqjzkfcklluotqpwganvksoqtzixkfkrtqobdnregwgkxjwzsruvhztscxjyqlhfytomzhxiglxemdhkjnskrsqngojffogrkbygmdgzfwrlhwhhngqpjpepqgynsdybhpuaqhgjroijqofiwnxgxdmhofwsjnmwitruiesefzmabcfsyzrrruidewjowfkwwwqhztsmmtdnejlqhkmbpmknlxijnmzbtqviburbqwufipqsrqplcelovsxz...

output:

0

result:

ok single line: '0'

Test #9:

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

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

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: 0ms
memory: 3664kb

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: 1ms
memory: 3960kb

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: 1ms
memory: 3820kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

131859070652

result:

ok single line: '131859070652'

Test #14:

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

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

781196173176

result:

ok single line: '781196173176'

Test #15:

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

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

4343956108320

result:

ok single line: '4343956108320'

Test #16:

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

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

18494567762260

result:

ok single line: '18494567762260'

Test #17:

score: 0
Accepted
time: 7ms
memory: 7716kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

32209183658799

result:

ok single line: '32209183658799'

Test #18:

score: 0
Accepted
time: 9ms
memory: 9780kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

54681136007004

result:

ok single line: '54681136007004'

Test #19:

score: 0
Accepted
time: 20ms
memory: 11896kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

29370598770431

result:

ok single line: '29370598770431'

Test #20:

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

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: 1ms
memory: 3752kb

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: 0
Accepted
time: 1ms
memory: 3772kb

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:

21735754192

result:

ok single line: '21735754192'

Test #23:

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

input:

abbbbabbbbbaaaabaabbbaaabaababaaababaababbbaaaabbaabbbabbaabbaabbbbbabbbbaabaabaabbbaabbaaaabaaabbab
bbbbbbbbbbbbab
224008866 420036954 610760159 229448373 88014692 800505315 190642695 680916401 526205898 463834969 506379052 591268851 942360508 176667947 891525614 324651315 294533169 355712507 94407...

output:

40969461750

result:

ok single line: '40969461750'

Test #24:

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

input:

baabaaabaabbbbabaaaabaaabaabbababbaaababbbaababbbaabbbababaaababbbaabbbabaaabbbabaabbaaabaaaaabaaabaaabaaaababbbbbbbabbabaabbbabababbbbbaaaaaaabbbbbbbbaababaababbbbbbaaaaaabbabbbabbbababababaaaaabbaaababbabbbbaaabbbaabaabaabaaabaabbbaaaaaabbaaaabbbbbbaabbabaabbbabbaaabababbbabaabbbbbabbbbbbababbbaab...

output:

158990471979

result:

ok single line: '158990471979'

Test #25:

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

input:

ababaababbbbbbababbbbaaabaaabbabababbabbabbabbbbbbabbabbbabbabaabbaaabbbababaabbbbbbbbabaabbaabababababababbabaaaabaaabbabbaabbbbabbabaabaabbabbababaababaaaabbaabaaaaaabbabbbaabababbabababbaabaabbaababbbbababbbbaabbbaabbbaabbabbaaabaabaababbabbabbabaaaaababbbbbaaaaaabababbaabbbbbbaabbbaaababbbabbaaa...

output:

532301963225

result:

ok single line: '532301963225'

Test #26:

score: 0
Accepted
time: 2ms
memory: 4572kb

input:

bbabbbaababaabbbabababbbaabbbbbbbbabaaaabbabbbaababaababbbbbabbbaabaabbabababaababaaabaaabbaabbaabbbabbbbbbbaabbaaabababbabababbbabbbaaabbbbbababbbbabbbabbababbabaabbbabaabbaabbabbaaabababbbaaabaaaabababaaabbbbbabbbaaabbbababbbbbbaaaabbbababbaabaabaabbaaaaabbababbabbbaaaabaaabbaaaaabbbbbbbbaabababbb...

output:

2701255525826

result:

ok single line: '2701255525826'

Test #27:

score: 0
Accepted
time: 7ms
memory: 6644kb

input:

abaabaababaaabaaaabaabaaabbabaaaabbbbbaabaaaaaaaaabaababbaaabbbbababbbabbaaaaabababbbbbabbabbaabbaababaabaaaaababbbbbabbabaabbaabbaaaaabaaababbabbabbabbbbbbbabaaababbbaaaaabbabaabaaaabbbbabbaababbabaaaaabaaabbbaaaaaaabbbababbbaaabbbbababbabaabbaabbaabaaabbabaabbaababbabaabbbbabababbbabbbababbbbaabba...

output:

12048672748205

result:

ok single line: '12048672748205'

Test #28:

score: 0
Accepted
time: 8ms
memory: 10412kb

input:

baabbababbaababaabbbaaaababbbbbbbbaaababbbbabbbabababbabaabbabaabbabaababbaabababaabbbabbabbbaaaabbbbbaabbbbbabbbaabbabaaababbabbbaaabaabbaaabbabaabbaaaaaabbbbaabbaabaaababbbbbbbabaabaaababbbbbaabbbaabaaaaaaaabbbbaabababbaabbbabbbababaaaabaaaaaababaabbaababaaaaabbaabaabaababbbbbababbbbbabbababaabbba...

output:

27307885756145

result:

ok single line: '27307885756145'

Test #29:

score: 0
Accepted
time: 10ms
memory: 12116kb

input:

abaaabaababaaabaabbaabaabaaabbbabaabaabaabaaabaaabababbbbaabbbbabababaaababbbbbbbaabbaaaaababaaaaabbababaaabbbabaaabbbbbaaabbabbababaabbabaabaabaabbabaaaaabaaababbbaaabababaabbbbbbbbaabbbababbaabbbbabababababbbbbabaababbaabbabababbbaaaabaabbaabbaaabbabbabbabaabbbbbabbbabbaaabaaaabababaabaaabbbabbaaa...

output:

60650729660703

result:

ok single line: '60650729660703'

Test #30:

score: 0
Accepted
time: 19ms
memory: 15472kb

input:

bbabbaabaaaabbbbbaaabbaaabbbbbabaaababbbbbbaaabaababbbbaabaaaaabaaabbaabbbabbbbabbbbbababaabababbbbbaabbabbbabbaabbbbabaaaaababbaababbbbabaabbbababababaabaabaaabbabbbbbabbbbbaaabaabbbabaabbbbbaababbabbbabababbaababaaaabaaabbbabaaababbbabaaabbabbbbabbbaabaaaaabaabaabbbbbbbabbbabababbbbababbabbbaabaaa...

output:

52715304867225

result:

ok single line: '52715304867225'

Test #31:

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

input:

babbabcbbc
b
873567223 881484594 836115671 468572820 185039216 58091481 170367767 818219310 963479412 251616100

output:

4543074182

result:

ok single line: '4543074182'

Test #32:

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

input:

abbabbcbcbbccbcbabacbaaabbaacc
abcbcbabacaaa
386691218 263581484 792579023 190122423 603222485 665656812 488069118 788157772 204045179 809683860 674555380 635625335 958310740 397232780 513421533 618027657 978559874 446435249 835921781 364825227 712870653 425294036 620268685 595633077 61877266 905874...

output:

9093474017

result:

ok single line: '9093474017'

Test #33:

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

input:

abaaaabbcbcbbcccacccaccbbbabacbbcacbbbcaccbacaaaca
aabbcbbb
415624183 868426443 266605422 250181024 635044324 920618613 953131881 7130518 634406136 458071208 900865957 935331579 317113106 239502115 983885607 310558150 293823233 371972022 820796715 45701953 271074059 161994440 234839966 401821838 804...

output:

17954653966

result:

ok single line: '17954653966'

Test #34:

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

input:

acabaccbbbbbcbabbaaabacbbaacaacaaacbcbacbaacaccbbcabcccbaacbacaaaababcaaaabcacabcaaaaabbaaacccbbbacb
cccccccccccccbcbaabaaaaababaaaaaaaaaaaaaaa
913277002 53312678 245884665 867635375 292615331 842124556 969422704 310509309 496152054 153362714 559283236 853594334 346932833 468897897 358165748 9865386...

output:

26421982372

result:

ok single line: '26421982372'

Test #35:

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

input:

accbcbcbaacbcbbaacaabbabbccbbcbaacacccbacaacabcabcacbabacababaaaabbcacacabaacacbacbaccaaabcbbaabcbccbbcccccbbbcacabbcbabcacbababbcbcaaabbbcbaabccbbbbbbaccaccbaccbacccaaccacccaabcacacacbacbcbbaaccbbbaabbbbcbcabbbaaacbbcbcaaaabbbacbcbbcbcabacacabcaccacbaaaabaabcccabaabbaccccbbcaacacbbabababccbbaccacaa...

output:

186216587955

result:

ok single line: '186216587955'

Test #36:

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

input:

cbcbaabbaaabbbccbbabbbbaccbbbbabaacbabbcbacabbaacacacaaacccbcbabcaccbccaababbbccaaaabbacabacabbaacbcabaacbbaccccaacacacaabcabcbcbacccaaabbaacccaacbbaabaabaabbbcacaaaacaacaccccacbbbcacaabbcabaaaaccabaaaccbbcabbccbcbcbcbbbabbccaaacbccaacaacbcacbaaabccbabacaccbbaacbabcaaacaaabbabcbbccacaacacabacbbcaccc...

output:

1134066452635

result:

ok single line: '1134066452635'

Test #37:

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

input:

acbacabbcbaaaaccbcaccaabaaabcabbcccabacbbaaacbbcbabbbbccabbbbbccacabbcacaaccbbbcabacccbbcccbcbaaccccccabbaabbabbbcbaacbaaaacacbbbbaacabacaaaccaaabbcabbbccbbaacaaabcbcabaacaacbcaaabaaacabbcaabbbaacccbacabaccccabaccbabbbccbbcacbbcbaccccbbaaaacabbcbababcacccabacbaacacbcabbbbcababacbbcaabbbbacbbabcccbca...

output:

2512968763689

result:

ok single line: '2512968763689'

Test #38:

score: 0
Accepted
time: 9ms
memory: 6980kb

input:

acbacbbaaaacccbcbccaabccacbaabbcbcaccbccbaabcaaacacbbbbcccaccaaaccabcabcbbbababacbbcbbabbcbbbacaabaccaaaabccabbacbacaacaccabbaccbbbcbbbbbaabaaabbabccbbbbaabaacaaabccaabcbccbcccbabaacaabbbbccbbabbacababbcaacbabcabcacaaacacaccaaccbaaabaacccaaacccbbbbacbcbccabaaaabcccacabbbacabcbbbbcabaacbccaacccbcbaaa...

output:

13386866355959

result:

ok single line: '13386866355959'

Test #39:

score: 0
Accepted
time: 17ms
memory: 9156kb

input:

cabbcaaccccbcacccabacabbabbabbacabacbbcbaabbccaccbbacabccaabcbacccbcaaacccccbcbbbaaabaabbcacbcbaabaaccacbcaacbaccaaccabbcccccabccbbbbaaacbabaaaabbaabacaccbccbccbacbcbaacbabacaabcabcbcabcabbcaccabaacccaacaccabbccbcbaacbccaabbccabccccbbcaacacbbbbbabbbbcacaaabcbcbcacbcbcacbbcbacbaaaaabacabbbacbbacbbbaa...

output:

32509001047635

result:

ok single line: '32509001047635'

Test #40:

score: 0
Accepted
time: 24ms
memory: 26020kb

input:

bacbbcbcaccbaaaaaaaccbcacccacabcbcbbaccaacabbacacacacbccacccababaaaccabccccccbaabbbaabbbbbccbccaabbaaacccbcaccaabaaacabcabcabacbabaccbabccaccbabcccbcabccaccbacaaabbcbacaccbbccaaaacaccaabacbbabbababaaacabbbccbcbacbacabaaacabbacbabaabbaaabaabaabcacbbccbaababbbcacccabaacbacbbbcaaaaaacabbccbacbabaaabbbb...

output:

65137117512545

result:

ok single line: '65137117512545'

Test #41:

score: 0
Accepted
time: 25ms
memory: 31508kb

input:

abaccbaaccbabcacbcbcbccbabacbaccccabaaccbbcaaabaccbcccccbcbacacbcabacabbbbcabaabbbcaccabcbcaaaacbbaaaaccccacacbacbbcbbaacacacaaacccbabcaabccbbccabaaaacaacacacbcbacccabbbbbccbacbcbbcbcabababbaaabaacababbbcbaabacacbbbcbacbacbcaaaabbcbaacacaacccbccbcbacbaabbbaababcaabcbbbbcabcacccabaabaaaccbabaccacaccc...

output:

71532659305323

result:

ok single line: '71532659305323'

Test #42:

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

input:

cdaaaaccca
ccca
975318493 593748055 811598160 192786675 443146435 685638445 234591027 505590004 732796904 863809533

output:

3459714674

result:

ok single line: '3459714674'

Test #43:

score: -100
Runtime Error

input:

dbadadbcacccccaadbbbcddcbacacb
bcccbbbdbaab
881472404 308808857 738133915 354072455 544742284 929404357 797394290 936671664 932546509 893722277 42383542 290795717 430812999 971357431 97809721 635309874 555467981 193228540 875991792 218698285 611406745 281504760 187661429 241476139 540326342 10976734...

output:


result: