QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #504616 | #275. Palindromes | JohnAlfnov | 0 | 1ms | 8056kb | C++14 | 790b | 2024-08-04 14:06:39 | 2024-08-04 14:06:39 |
answer
#include<bits/stdc++.h>
using namespace std;
char s[300005];
int fi[300005],cd[300005];
int lb[300005][26],dep[300005];
int zw[300005],cs[300005];
int main(){
scanf("%s",s+1);
int n=strlen(s+1);
fi[0]=-1,cd[0]=-1;
fi[1]=0,cd[1]=0;
int tt=1,sl=tt;
for(int i=1;i<=n;++i){
int wz=sl;
while(1){
if(s[i]==s[i-cd[wz]-1])break;
wz=fi[wz];
}
if(!lb[wz][s[i]-'a'])lb[wz][s[i]-'a']=++tt,cd[tt]=cd[wz]+2;
int cz=lb[wz][s[i]-'a'];
wz=fi[wz];
while(~wz){
if(s[i]==s[i-cd[wz]-1])break;
wz=fi[wz];
}
if(~wz)fi[cz]=lb[wz][s[i]-'a'];
else fi[cz]=1;
zw[i]=sl=cz;++cs[zw[i]];
}
for(int i=n;i>=1;--i)cs[fi[zw[i]]]+=cs[zw[i]];
long long ans=0;
for(int i=1;i<=tt;++i)ans=max(ans,1ll*cd[i]*cs[i]);
printf("%lld\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 8
Accepted
time: 0ms
memory: 7984kb
input:
abacaba
output:
7
result:
ok single line: '7'
Test #2:
score: 8
Accepted
time: 1ms
memory: 5944kb
input:
www
output:
4
result:
ok single line: '4'
Test #3:
score: 8
Accepted
time: 1ms
memory: 7860kb
input:
abacababa
output:
9
result:
ok single line: '9'
Test #4:
score: 8
Accepted
time: 1ms
memory: 6012kb
input:
r
output:
1
result:
ok single line: '1'
Test #5:
score: 8
Accepted
time: 1ms
memory: 7984kb
input:
xd
output:
1
result:
ok single line: '1'
Test #6:
score: 8
Accepted
time: 1ms
memory: 7860kb
input:
dd
output:
2
result:
ok single line: '2'
Test #7:
score: 8
Accepted
time: 1ms
memory: 7904kb
input:
opo
output:
3
result:
ok single line: '3'
Test #8:
score: 8
Accepted
time: 1ms
memory: 7968kb
input:
opoo
output:
3
result:
ok single line: '3'
Test #9:
score: 8
Accepted
time: 1ms
memory: 7968kb
input:
abacabadabacaba
output:
15
result:
ok single line: '15'
Test #10:
score: 8
Accepted
time: 1ms
memory: 7908kb
input:
xxxxxyxxxxyxxxxx
output:
24
result:
ok single line: '24'
Test #11:
score: 8
Accepted
time: 1ms
memory: 7884kb
input:
xxxyxxxyzzzabcdxxdcba
output:
10
result:
ok single line: '10'
Test #12:
score: 8
Accepted
time: 1ms
memory: 8056kb
input:
qpppppppwowpppppq
output:
24
result:
ok single line: '24'
Test #13:
score: 8
Accepted
time: 1ms
memory: 7968kb
input:
mqmwmemrmtymmmmmmmmqwertyeeeeeeeee
output:
25
result:
ok single line: '25'
Test #14:
score: 0
Wrong Answer
time: 1ms
memory: 5936kb
input:
mqmwmmmmmemrmtymmmmmmmmqwertyeeeeeeeee
output:
64
result:
wrong answer 1st lines differ - expected: '28', found: '64'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%