QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#672288 | #9514. 研心 | jinqihao2023 | 100 ✓ | 881ms | 723892kb | C++14 | 9.3kb | 2024-10-24 16:18:16 | 2024-10-24 16:18:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=8e5+5,p1=19491001,mod1=1e9+9,B=120,M=3.5e3+5;
ll ansall;
int n,m,ls[N],lt[N],mxs[N],mxt[N],pw1[N];
string s[N],t[N];
vector<bool>iscs[N],isct[N];
vector<int>h1[N],h2[N],h3[N],h4[N];
int hs1(int p,int l,int r){return (h1[p][r]-1ll*h1[p][l-1]*pw1[r-l+1]%mod1+mod1)%mod1;}
int hs2(int p,int l,int r){return (h2[p][l]-1ll*h2[p][r+1]*pw1[r-l+1]%mod1+mod1)%mod1;}
int hs3(int p,int l,int r){return (h3[p][r]-1ll*h3[p][l-1]*pw1[r-l+1]%mod1+mod1)%mod1;}
int hs4(int p,int l,int r){return (h4[p][l]-1ll*h4[p][r+1]*pw1[r-l+1]%mod1+mod1)%mod1;}
void init()
{
pw1[0]=1;for(int i=1;i<N;i++)pw1[i]=1ll*pw1[i-1]*p1%mod1;
for(int i=1;i<=n;i++)
{
iscs[i].resize(ls[i]+1),h1[i].resize(ls[i]+2),h2[i].resize(ls[i]+2);
for(int j=1;j<=ls[i];j++)h1[i][j]=(1ll*h1[i][j-1]*p1+s[i][j])%mod1;
for(int j=ls[i];j>=1;j--)h2[i][j]=(1ll*h2[i][j+1]*p1+s[i][j])%mod1;
for(int j=1;j<=ls[i];j++)
{
int l=1,r=min(j,ls[i]-j+1),res=0;
while(l<=r)
{
int mid=l+r>>1;
if(hs1(i,j,j+mid-1)==hs2(i,j-mid+1,j))l=mid+1,res=mid;
else r=mid-1;
}
mxs[i]=max(mxs[i],res);
if(res==ls[i]-j+1)iscs[i][j]=1;
}
}
for(int i=1;i<=m;i++)
{
isct[i].resize(lt[i]+1),h3[i].resize(lt[i]+2),h4[i].resize(lt[i]+2);
for(int j=1;j<=lt[i];j++)h3[i][j]=(1ll*h3[i][j-1]*p1+t[i][j])%mod1;
for(int j=lt[i];j>=1;j--)h4[i][j]=(1ll*h4[i][j+1]*p1+t[i][j])%mod1;
for(int j=1;j<=lt[i];j++)
{
int l=1,r=min(j,lt[i]-j+1),res=0;
while(l<=r)
{
int mid=l+r>>1;
if(hs3(i,j,j+mid-1)==hs4(i,j-mid+1,j))l=mid+1,res=mid;
else r=mid-1;
}
mxt[i]=max(mxt[i],res);
if(res==j)isct[i][j]=1;
}
}
}
namespace work1
{
bool iscor[N],ved[N];
int minn[N];
struct SAM
{
struct Tree{int ch[26],fa,len,sz,ch1[26],edp;}t[N];
int tot;
vector<int>son[N];
void dfs1(int x)
{
if(ved[t[x].edp])iscor[x]=1,minn[x]=t[x].edp;else minn[x]=2e9;
for(auto y:son[x])dfs1(y),iscor[x]|=iscor[y],minn[x]=min(minn[x],minn[y]);
}
void build(string s)
{
int len=s.length()-1,lst=0;
for(int i=1;i<=len;i++)
{
int k=s[i]-'a',p=lst,now=++tot;
t[now].len=t[lst].len+1,t[now].sz=1,t[now].edp=i;
while(1)
{
if(!t[p].ch[k])t[p].ch[k]=now;
else
{
int q=t[p].ch[k];
if(t[q].len==t[p].len+1)t[now].fa=q;
else
{
int nq=++tot;t[nq]=t[q],t[nq].len=t[p].len+1,t[nq].sz=0;
t[q].fa=t[now].fa=nq;
while(t[p].ch[k]==q){t[p].ch[k]=nq;if(!p)break;p=t[p].fa;}
}
break;
}
if(!p)break;
p=t[p].fa;
}
lst=now;
}
for(int i=1;i<=tot;i++)
{
son[t[i].fa].push_back(i);
int pos=t[i].edp-t[t[i].fa].len;
t[t[i].fa].ch1[s[pos]-'a']=i;
}
dfs1(0);
}
void clr()
{
for(int i=0;i<=tot;i++)
{
minn[i]=0,iscor[i]=0;
for(int j=0;j<26;j++)t[i].ch[j]=t[i].ch1[j]=0;
t[i].fa=t[i].len=t[i].sz=t[i].edp=0;
son[i].clear();
}
tot=0;
}
}sam;
int res[M][M],ps[M],pt[M];
void slv()
{
int cnts=0,cntt=0;
for(int i=1;i<=n;i++)if(ls[i]>B)cnts++,ps[cnts]=i;for(int i=1;i<=m;i++)if(lt[i]>B)cntt++,pt[cntt]=i;
for(int i=1;i<=cnts;i++)for(int j=1;j<=cntt;j++)res[i][j]=max(mxs[ps[i]],mxt[pt[j]]);
for(int i=1;i<=cnts;i++)
{
for(int j=0;j<=ls[ps[i]]+1;j++)ved[j]=0;
sam.clr();
for(int j=1;j<=ls[ps[i]];j++)if(iscs[ps[i]][j])ved[j-(ls[ps[i]]-j+1)]=1;
sam.build(s[ps[i]]);
for(int j=1;j<=cntt;j++)
{
int p=0;
for(int k=1;k<=lt[pt[j]];k++)
{
if(k-1==sam.t[p].len)
{
if(sam.t[p].ch1[t[pt[j]][k]-'a'])p=sam.t[p].ch1[t[pt[j]][k]-'a'];
else break;
}
else
{
if(s[ps[i]][sam.t[p].edp-k+1]!=t[pt[j]][k])break;
}
if(!iscor[p])break;
res[i][j]=max(res[i][j],(ls[ps[i]]-minn[p]+1)/2+k);
}
}
for(int j=1;j<=m;j++)if(lt[j]<=B)
{
int p=0,ress=mxs[ps[i]];
for(int k=1;k<=lt[j];k++)
{
if(k-1==sam.t[p].len)
{
if(sam.t[p].ch1[t[j][k]-'a'])p=sam.t[p].ch1[t[j][k]-'a'];
else break;
}
else
{
if(s[ps[i]][sam.t[p].edp-k+1]!=t[j][k])break;
}
if(!iscor[p])break;
ress=max(ress,(ls[ps[i]]-minn[p]+1)/2+k);
}
if(ress>B)ansall+=ress-B;
}
}
for(int i=1;i<=cntt;i++)
{
for(int j=0;j<=lt[pt[i]]+1;j++)ved[j]=0;
sam.clr();
string tt=" ";
for(int j=lt[pt[i]];j>=1;j--)tt+=t[pt[i]][j];
for(int j=1;j<=lt[pt[i]];j++)if(isct[pt[i]][j])ved[lt[pt[i]]-2*j+1]=1;
sam.build(tt);
for(int j=1;j<=cnts;j++)
{
int p=0,len=0;
for(int k=ls[ps[j]];k>=1;k--)
{
len++;
if(len-1==sam.t[p].len)
{
if(sam.t[p].ch1[s[ps[j]][k]-'a'])p=sam.t[p].ch1[s[ps[j]][k]-'a'];
else break;
}
else
{
if(tt[sam.t[p].edp-len+1]!=s[ps[j]][k])break;
}
if(!iscor[p])break;
res[j][i]=max(res[j][i],(lt[pt[i]]-minn[p]+1)/2+len);
}
}
for(int j=1;j<=n;j++)if(ls[j]<=B)
{
int p=0,len=0,ress=mxt[pt[i]];
for(int k=ls[j];k>=1;k--)
{
len++;
if(len-1==sam.t[p].len)
{
if(sam.t[p].ch1[s[j][k]-'a'])p=sam.t[p].ch1[s[j][k]-'a'];
else break;
}
else
{
if(tt[sam.t[p].edp-len+1]!=s[j][k])break;
}
if(!iscor[p])break;
ress=max(ress,(lt[pt[i]]-minn[p]+1)/2+len);
}
if(ress>B)ansall+=ress-B;
}
}
for(int i=1;i<=cnts;i++)for(int j=1;j<=cntt;j++)if(res[i][j]>B)ansall+=res[i][j]-B;
}
void solve()
{
slv();
}
}
namespace work2
{
vector<int>temps,tempt;
struct Trie
{
int ch[N][26],dfn[N],iscor[N],sign,L[N],R[N],maxd,sum[N],dep[N],tot,ed[N],pos[N];
vector<int>sd[N];
vector<pair<int,int> >son[N];
void ins(string s,vector<bool>ss,int pp)
{
int len=s.length()-1,p=1;
for(int i=1;i<=len;i++)
{
int k=s[i]-'a';
if(!ch[p][k])ch[p][k]=++tot;
p=ch[p][k];
if(i%2==1 && ss[i/2+1])iscor[p]=1;
}
maxd=max(maxd,len),ed[p]++,pos[pp]=p;
}
void dfs1(int x,int nd)
{
dep[x]=nd;
sd[nd].push_back(x);
L[x]=dfn[x]=++sign;
for(auto y:son[x])dfs1(y.first,nd+1);
R[x]=sign;
}
void build()
{
sd[0].push_back(1);
for(int i=1;i<=tot;i++)for(int j=0;j<26;j++)if(ch[i][j])son[i].push_back({ch[i][j],j});
dfs1(1,0);
for(int i=1;i<=tot;i++)sum[dfn[i]]+=ed[i];
for(int i=1;i<=tot;i++)sum[i]+=sum[i-1];
}
}S,T;
struct Seg_tree
{
struct STree{int l,r,num,minn,add;}t[N*4];
void pushup(int p)
{
t[p].minn=min(t[p*2].minn,t[p*2+1].minn),t[p].num=0;
if(t[p*2].minn==t[p].minn)t[p].num+=t[p*2].num;
if(t[p*2+1].minn==t[p].minn)t[p].num+=t[p*2+1].num;
}
void update(int p,int v){t[p].add+=v,t[p].minn+=v;}
void pushdown(int p){if(t[p].add)update(p*2,t[p].add),update(p*2+1,t[p].add),t[p].add=0;}
void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r,t[p].minn=0,t[p].num=S.sum[r]-S.sum[l-1],t[p].add=0;
if(l==r)return ;int mid=l+r>>1;
build(p*2,l,mid),build(p*2+1,mid+1,r),pushup(p);
}
void change(int p,int l,int r,int v)
{
if(l<=t[p].l && t[p].r<=r)return update(p,v);pushdown(p);
int mid=t[p].l+t[p].r>>1;
if(l<=mid)change(p*2,l,r,v);if(mid<r)change(p*2+1,l,r,v);pushup(p);
}
}t1;
struct abc{int l,r,v;};
vector<abc>que[N];
void solve()
{
S.tot=1,T.tot=1;
for(int i=1;i<=n;i++)
{
string ns=" ";vector<bool>ss;ss.push_back(0);
for(int j=ls[i];j>=1;j--)ns+=s[i][j],ss.push_back(iscs[i][j]);
S.ins(ns,ss,i);
}
for(int i=1;i<=m;i++)T.ins(t[i],isct[i],i);
S.build(),T.build();
vector<pair<int,int> >temp;
ll ans=0;
for(int i=1;i<=B;i++)
{
int sss=0,sst=0;
for(int j=1;j<=T.tot;j++)que[j].clear();
for(int j=1;j<=n;j++)if(mxs[j]>=i)que[T.L[1]].push_back((abc){S.L[S.pos[j]],S.L[S.pos[j]],1});
for(int j=1;j<=m;j++)if(mxt[j]>=i)que[T.L[T.pos[j]]].push_back((abc){S.L[1],S.R[1],1}),que[T.L[T.pos[j]]+1].push_back((abc){S.L[1],S.R[1],-1});
vector<pair<int,int> >temp1;
for(auto j:temp)for(auto k:S.son[j.first])if(T.ch[j.second][k.second])temp1.push_back({k.first,T.ch[j.second][k.second]});
if(i>=2)
{
for(auto j:S.sd[i*2-3])if(S.iscor[j])for(auto k:S.son[j])if(T.ch[1][k.second])temp1.push_back({k.first,T.ch[1][k.second]});
for(auto j:T.sd[i*2-3])if(T.iscor[j])for(auto k:T.son[j])if(S.ch[1][k.second])temp1.push_back({S.ch[1][k.second],k.first});
}
sort(temp1.begin(),temp1.end()),temp1.erase(unique(temp1.begin(),temp1.end()),temp1.end());
for(auto j:temp1)que[T.L[j.second]].push_back((abc){S.L[j.first],S.R[j.first],1}),que[T.R[j.second]+1].push_back((abc){S.L[j.first],S.R[j.first],-1});
t1.build(1,1,S.tot);
for(int j=1;j<=T.tot;j++)
{
for(auto k:que[j])
{
t1.change(1,k.l,k.r,k.v);
}
ans+=(T.sum[j]-T.sum[j-1])*(n-(t1.t[1].minn!=0?0:t1.t[1].num));
}
temp=temp1;
sort(temp.begin(),temp.end()),temp.erase(unique(temp.begin(),temp.end()),temp.end());
}
ansall+=ans;
}
}
int main()
{
// freopen("mirror.in","r",stdin);
// freopen("mirror.out","w",stdout);
scanf("%d %d",&n,&m);
int ss=0,tt=0;
for(int i=1;i<=n;i++)cin>>s[i],ls[i]=s[i].length(),s[i]=' '+s[i],ss+=ls[i];
for(int i=1;i<=m;i++)cin>>t[i],lt[i]=t[i].length(),t[i]=' '+t[i],tt+=lt[i];
init();
work2::solve();
work1::solve();
printf("%lld\n",ansall);
return 0;
}
詳細信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 42ms
memory: 313668kb
input:
10 100 aabaababaaaababbabaaaababaababbbaabbbaabaabaabbbaababaaababbaababababbbaababbbbbbbbaabbbbaabbbbbbbbaabaabbbaabbbbbabbbbbaabbbaabaa bbaaabaabbbbaaabaaaaabbbbbabaabbabbaabbaabbaabbabbababaabaabbaabbbbbbaaaabbbbabaaaabaaabbbabaaaaaabbaaaabbbabbbbbaaaabbabaababbaabbaaabbbbbbaaaabbbababaabbaaaba b...
output:
10468
result:
ok single line: '10468'
Test #2:
score: 20
Accepted
time: 47ms
memory: 315100kb
input:
10 100 abbacbbaabababcaabbaabbbabcaccabcabbabbbccaacabaabacccbacaaabbaaabbbaacaabbabcabbbcbacaaaaabaaaabaaacbbccbacacbbaaccacbabcbccacbaaacaaacccbabbaccacaaacaabbbccaaccbbabaabcbbcbcbb bccabcacbacccbcababaccccaaabbccacaccccabbaabbcacabaccabacbbbaaaabaabccbcaacaaccbcacabcbbbcccccabccbaababccccabcabab...
output:
6384
result:
ok single line: '6384'
Test #3:
score: 20
Accepted
time: 43ms
memory: 317232kb
input:
50 50 aaaaabbabbbbbaababbaaaababaababababbbbaabaaaaaaaabaabbaaabaaaabaaabaabbbabbbababbbbabbbabbaaababbabaabbabbabbabbaaababaaaaabbbbbbaabaabaabbbbbabaaababb abbabbbaabaaaaabababaabbabaabbbbab bababbbbaabaabbaabbbbaabaabbbaabbbbaaabbabbbaaabbbbaaabaabbaaaaaabbbabaaaaabbaabaabaaabaaababbbbbaaabbbbbba...
output:
21362
result:
ok single line: '21362'
Test #4:
score: 20
Accepted
time: 74ms
memory: 349732kb
input:
50 50 aababcabbbcbaacaaaaccababbacbbaaabcbaaccabbababbcccaacaaaacacbcbaaabaacabbbbbbaccaaacbbacaacacbcccbbacabbcbcbacababcbbacaccaacacbcccbababaccabccccbabaccababccccbcbabcabcabccaaccababcbccacbbaaaacc cbaccababccbaaacbccabbcccacacacaaaabaaababcacabaccbccacbcbaaaaabbacbbaccabba ccbcbcacbcaccabbbccaa...
output:
13421
result:
ok single line: '13421'
Test #5:
score: 20
Accepted
time: 46ms
memory: 345980kb
input:
1000 1000 a aabbab bbbbababbbba bb baaaaa ba a baa a bbaaaabaaaba ba a a a bbababbbbbb b aaabb bbbbbaabbabab bbaaa aaaa aa aaaaaababb a bbaba baaa aabbab babaab b aab bbbabb aaaabbbbbaaaaaa bbbbbbbaabab bb ab aaa aaababb babaaaabab aa aaabaaababa abbabaaaaabb bbaa abaabb baa abba aaaa abbbb aab b aa...
output:
3159935
result:
ok single line: '3159935'
Subtask #2:
score: 30
Accepted
Test #6:
score: 30
Accepted
time: 809ms
memory: 710696kb
input:
1 10000 bcacacbcdadbcbccbdddaaddabcaccccbaabbcdcdaabdacccadacbbbabdaaacadacdccadcbdadadcaaabdbdbdcdcccbacbdbccacbdadcaaaacbabdadcacdcacadcadaabdaaabccccdcbcdbcadcaabbbaacaadaccdaccadbddcdbccbcddcaadcaadaadbbaadbcdbddbcbadbccbaddaacabcdccbadaddcadcbababccabcaadbcbdbcbbcdcbdbcdbdaaddbacddcabbbdccbddba...
output:
1160913325
result:
ok single line: '1160913325'
Test #7:
score: 30
Accepted
time: 816ms
memory: 723892kb
input:
1 1000 caaadbacdaaccbdcaccbdbddcdaccaaaaaccdccaadbadbcdccaacdadcccaddadcbacbbdcaadbbcdaddcadddccdbabccdadcaacabcabbbdbbbbdbbaaccddcdddcddddddbdbbadbddcbacdcdbdabcbbdbbaaadbdacaccdbaaabacbacabdaccaabaadddccbabacdbdddbdcadadcdccabaabbccbacddddcbcdbabaadaddbbdabadaccbdbaaabdadadaadabbdbadacacbdcbcbdccc...
output:
134272327
result:
ok single line: '134272327'
Test #8:
score: 30
Accepted
time: 779ms
memory: 716944kb
input:
1 10000 bbcbcaacaaaacacbacacbaacbacbaababaacacbacbacbccaacbbacbbccababcaaaccabaaccbbbaaaabbababaacbbccabcaccaaccbacccaacabcaacacaccababbbbbcbacaaabbcbaccacaaaaabbacbbcbbcabccaabcabcabaabbbabbababbabcacbcaccabacaababbacccabbcaaacacccbcbcccbbbbaababbabcaaabaccccbbbabccabacbcbabccccaccbcccccbcccccccbbc...
output:
1375114968
result:
ok single line: '1375114968'
Test #9:
score: 30
Accepted
time: 780ms
memory: 720304kb
input:
1 10000 cbaacaaaaccacaacbbcacabccbbabbababbababbacbababbcabcbacabbaaaacccacbbaaacacbacccbababaabccbbcabbbcaacbcbbbcbcbccccbabcacccccaabbbccacccacabccbcccbaaaccbbbacbaabbcbaabccccaabacabccaaccbbbaccbbcbcaabcaacbcbbcacbcbcabbacbababcbcabcbaabbbbbcccccbcacbabbcccccaacccbaccbaacbccbcababbabcbbccbbbbacab...
output:
1363955024
result:
ok single line: '1363955024'
Test #10:
score: 30
Accepted
time: 794ms
memory: 711584kb
input:
1 10000 aacbabccacabcccbccbbcacbbcbcacbbcacbbcbcacacbaaabbbbccaabcbbccccaccccbbcbbcacbbcbbcacbbcbcacacbaaabbbbccaabcbbccccaccccbbcbcbbccccaccccbbbccccaccccbbcbcbbccccaccccbbcbaaccbbbbaaaaabbbbccaabcbbccccaccccbbcbcbbccccaccccbbbccccaccccbbcbcbbccccaccccbbcbaaccbbbbaaabcacacbcbbcacbbcacacbaaabbbbccaa...
output:
1951994915
result:
ok single line: '1951994915'
Test #11:
score: 30
Accepted
time: 808ms
memory: 713584kb
input:
1 10000 bbaabbaaaabbbaaabbbaabaabaababbbbbabaabbababaaabbbbbbabbaaaabbbbbbaabababbbbabbaababbbbabaabaabaaabbabababbbbbaabababbaabbabbbababbbabaaaaabaaaaaaabaabaaabababbbabbabbaaaabababbbbabaabbaaababbaabbbbabbabbabbabbabaababaaaabbbaabbaababbabbbbaaaaaaaaaababbbbabbbabbaabbbbaaabaabbbbbaabbaababbaba...
output:
424739578
result:
ok single line: '424739578'
Subtask #3:
score: 20
Accepted
Test #12:
score: 20
Accepted
time: 725ms
memory: 516048kb
input:
100 1000 abbabbbbabbbbabaabaabbbbabaaabbbaabaabbabaabaabbaabbaabbababbabbababbbaabaabbaabbbabaabbbaaaabaaaabaababbaaaaaaaaabaabbaababbbbbbabbbabbbbababbbaaaaaabaaaabaaabbabbaaaaabbbabbabaabbabababbaaababbbaaaabbabbbabbabbabbbbbbabaabaabbbaabaaabbaabbabbbbaabbabaaabaabaabbbabbbbbabaababbbabababaabbba...
output:
1289287
result:
ok single line: '1289287'
Test #13:
score: 20
Accepted
time: 729ms
memory: 512520kb
input:
1000 1000 babbbabaabaaaabbbbbababaaabbaabbbbbabbaababbbbaaabbbbaaabbbababbaaaabaaabbbbbbbbaabbabbbabbabbaaabaabbbbbbbababaabbbbabaaabbaaaaabbbaababbaaaaabbbbaaaabbbaabaaababaaabbabbbabbabbbabbaabbabbbabaaaaaabaabbabbababbbbbabaaabbbbababbbaabbbaaabbababaababbbbbaaabbbabbabaaaababbbaabaaaabbbabaaabbb...
output:
10431998
result:
ok single line: '10431998'
Test #14:
score: 20
Accepted
time: 822ms
memory: 504984kb
input:
1000 10000 babbababbbaaaaaaaaababbabbbababbbbbbbbabaaaaaabbaababbbbbbbaaaabbaaaaabbbbbbbababbabaaaaabbaaabaaaaaaabbbabbabbaaabbbabbbbababababbabbababbabbbbaabbbbaababbaababbababbbaaabbbbaaabaaaabababbbbaabaababbabbbaabbbbbabbbaaabaabaabbaabaaaaabbabbbbaaabbabbbaababbbaabaaaabbbababbbbbbbabababbaabab...
output:
94347164
result:
ok single line: '94347164'
Test #15:
score: 20
Accepted
time: 881ms
memory: 487724kb
input:
10000 10000 bbbabbaababbbbbababbbbaabbabaaaababbabbbabababaaaaaababbbaabaabbababbbbbaa b aaabbbbbbabbaabbbbbbaabaaababbbabbabaaabababbababaaabbaabaabaabbbbabb abbaabbaababbbabaabababaaaaaaaabaabbbb bbbbbabbaabbaaaabaabaababbbababbbbbaaaabbabbbabbaabbbabaaababababaabbaaaabaabbaaabbbaaaaaababababbbabb...
output:
694099162
result:
ok single line: '694099162'
Test #16:
score: 20
Accepted
time: 759ms
memory: 524548kb
input:
100 100 ababababbbababbabbaabbbbbaabaaaaabbabaaaaabbbaabbbabababbbaaaaababbaabbbababaababbaabbaaababaabbaabbbbbbaaababbbaabaaaababbaababbbaaaabbbbaababaabaabaaabaaaabaababaaababbbbabbaabbbbababbaaabaaabaabaabaaaabaaaabbbbbabaaaabababaaababbbbbabbaaaabbbaaaaaaabababbaaababbbabbbbbaaaaaaaaaabbaabababa...
output:
138444
result:
ok single line: '138444'
Subtask #4:
score: 30
Accepted
Test #17:
score: 30
Accepted
time: 710ms
memory: 520352kb
input:
100 1000 bcbccabbbabacabaabbccbaaabbbbcbbbaaaacaaabbccbababbacbbabbbaccccccccbccabcaacbbccbbbbcaaacabcccaccbaacccbcbaaaccbcaaaaaaaabccaaaacccbabacbcababbacbbbcaabaaacbbcaccbaccccbbcbacabaacbcaccacbcbcbbcbccccbbcacccaabbabcaabbacabaaacccbbcbccbabbcbccbcbbbabbaabacbccbacababbacbababbbaacccacbabcabcaba...
output:
833103
result:
ok single line: '833103'
Test #18:
score: 30
Accepted
time: 731ms
memory: 515332kb
input:
1000 1000 cacccababcaaccbaaabcbcabcbbccbcbcbbcacbbcabcaaccabcccaacabccaacaaaababbbbbcbbcbcbbbcacbaabccaccbaacaaacabbbcbcbaabbcccacaababbbabcaabbaabaabaabaabccaacccbabcbaacccbbbccaacbbacacacaacccbcbcbaccbccaaacabaacbcbaacbcbacaccbacbbcaccbabbbabbbaccccbbbcacccccaacbbaaaccacabaaacaccabacacbaaaaacbacab...
output:
6757759
result:
ok single line: '6757759'
Test #19:
score: 30
Accepted
time: 769ms
memory: 503568kb
input:
1000 10000 cbacbccbcbbcccbbcccaacccbbbacbccaaaccabacaabacccbbbcbabcaacabbabbabcaaaabccbabcaaacaaabbbacccacabcacccaaababcacbaacaccbccbcaaaaaaaaccabbcaaaaabccacaacbccabacabcccaabbcaccbcabbccbabbbccaacbabcbacacabbaaaababbccbcbacbbbcaccaabacbcaabbaaacaacccaaabbbcabbbcccacacaccaacbccabccbcacbbbbbabcbabbc...
output:
61388196
result:
ok single line: '61388196'
Test #20:
score: 30
Accepted
time: 787ms
memory: 495296kb
input:
10000 10000 aababaaccbcbabaccbaccbcaaabbcbbbbacbcbababbccbccbbac cbcccccacaccabcbbbaaabcaaccabccccccbabacbbabbaaacbabccbcaacacbbbabbbbcbbcbcbaaccaccbabccabbbbbabcabcbcccababbcabaccbbccbaaacaabacbcbcbbabbcbaabcaccaaaccbbcacaaabcabacabccbaabbacabccacbabbaababb cacbcbabc caacccaabaaccbbbabaababbbbcbcac...
output:
462062051
result:
ok single line: '462062051'
Test #21:
score: 30
Accepted
time: 732ms
memory: 518980kb
input:
100 100 abcababbbbbcaccccbcacacabbccccbbccacbbabacabbbbacacaacaaabbcaabcaaaaabaaccbaaacbbcbbcabbaaababacabcccaabbcbbbbaaaacaabbbacbcabacbbccbbacacbaaabacabbcbbcaabaccababccaaababbcbcacbabababcbcccccccababcbbbaaabbacbaabbaababcabaacbccacbbaccbbbbcbbabbccaacbaccaaabaccbaacaaaaabbcaccbbbaaccaaccccbbbaa...
output:
90325
result:
ok single line: '90325'
Test #22:
score: 30
Accepted
time: 767ms
memory: 469256kb
input:
430 800 aaaccaccaacbcccbccbccaaaaaabccabbcbccabcacbcaabcbacbccbbacccaccabccacbbcccccbacaacbabbbaaaaacbbbcabacbccaabcabcbacccacbabaacacbcaacbabbabbbbbaacacabbaccaabcccbacbbabccccccbabbaaaaababcababaabcaabbcbbaaccaccabbaabcabccbbcbacacaaabcbaaccccbcbacbccacaaacbbaabaabccabaacbccccbbbbcabccbbcbbcbccaba...
output:
157989035
result:
ok single line: '157989035'
Test #23:
score: 30
Accepted
time: 189ms
memory: 358056kb
input:
400 400 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
40039936
result:
ok single line: '40039936'
Test #24:
score: 30
Accepted
time: 635ms
memory: 429812kb
input:
400 400 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbabaaaaabbbbaabbb...
output:
108484268
result:
ok single line: '108484268'