// in the name of ALLAH
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5, L = 26;
#define MID(l, r) ((l+r)>>1)
int LNF[N], LNZ[N], n;
long long dp[N][L], PS[N], T[N], rt, rtt;
char S[N];
void ah() { cerr << "!!!\n"; }
struct HS1{
int mod = 1e9+7, bs = 9973;
int zrb(int a, int b) { return(1LL*a*b%mod); }
int jm(int a, int b) { int tmp=(a+b)%mod; while(tmp<0) tmp+=mod; return(tmp); }
int pw(int a, int b) { int rt=1; for(;b;b>>=1){ if(b&1) rt=zrb(rt, a); a=zrb(a, a); } return(rt); }
int PS[N], RV[N], P[N], INV[N];
inline void ini(){
n = strlen(S);
P[0] = 1; for(int i=1;i<N;i++) P[i] = zrb(P[i-1], bs);
INV[N-1] = pw(P[N-1], mod-2); for(int i=N-2;~i;i--) INV[i] = zrb(INV[i+1], bs);
PS[0] = S[0]; for(int i=1;i<n;i++) PS[i] = jm(PS[i-1], zrb(S[i], P[i]));
RV[n-1] = S[n-1]; for(int i=n-2;~i;i--) RV[i]=jm(RV[i+1], zrb(S[i], P[n-i-1]));
}
int get(int l, int r){
int rt = PS[r]; if(l) rt=jm(rt, -PS[l-1]);
return(zrb(rt, INV[l]));
}
int getrv(int l, int r){
int rt = RV[l]; if(r+1<n) rt=jm(rt, -RV[r+1]);
return(zrb(rt, INV[n-r-1]));
}
} f1;
struct HS2{
int mod = 1e9+9, bs = 701;
int zrb(int a, int b) { return(1LL*a*b%mod); }
int jm(int a, int b) { int tmp=(a+b)%mod; while(tmp<0) tmp+=mod; return(tmp); }
int pw(int a, int b) { int rt=1; for(;b;b>>=1){ if(b&1) rt=zrb(rt, a); a=zrb(a, a); } return(rt); }
int PS[N], RV[N], P[N], INV[N];
inline void ini(){
n=strlen(S);
P[0] = 1; for(int i=1;i<N;i++) P[i] = zrb(P[i-1], bs);
INV[N-1] = pw(P[N-1], mod-2); for(int i=N-2;~i;i--) INV[i] = zrb(INV[i+1], bs);
PS[0] = S[0]; for(int i=1;i<n;i++) PS[i] = jm(PS[i-1], zrb(S[i], P[i]));
RV[n-1] = S[n-1]; for(int i=n-2;~i;i--) RV[i]=jm(RV[i+1], zrb(S[i], P[n-i-1]));
}
int get(int l, int r){
int rt = PS[r]; if(l) rt=jm(rt, -PS[l-1]);
return(zrb(rt, INV[l]));
}
int getrv(int l, int r){
int rt = RV[l]; if(r+1<n) rt=jm(rt, -RV[r+1]);
return(zrb(rt, INV[n-r-1]));
}
} f2;
bool C(int l, int r) { return(f1.get(l, r)==f1.getrv(l, r)&&f2.get(l, r)==f2.getrv(l, r)); }
int32_t main(){
scanf("%s", S);
f1.ini(); f2.ini();
for(int i=0;i<n;i++){
int l=0, r=n;
while(r-l>1){
int mid = MID(l, r);
int a=i-mid, b=i+mid;
if(a<0||b>=n) { r=mid; continue; }
if(C(a, b)) l=mid;
else r=mid;
}
LNF[i]=l;
rt+=l+1;
int ll=i-l, rr=i+l;
ll--; rr++;
l=0, r=n;
while(r-l>1){
int mid = MID(l, r);
int a=ll-mid, b=rr+mid;
if(a<0||b>=n) { r=mid; continue; }
if(f1.get(a, ll-1)==f1.getrv(rr+1, b)&&f2.get(a, ll-1)==f2.getrv(rr+1, b)) l=mid;
else r=mid;
}
dp[ll][S[rr]-'a']+=l+1;
dp[rr][S[ll]-'a']+=l+1;
}
for(int i=0;i<n-1;i++){
int l=-1, r=n;
while(r-l>1){
int mid = MID(l, r);
int a=i-mid, b=i+mid+1;
if(a<0||b>=n) { r=mid; continue; }
if(C(a, b)) l=mid;
else r=mid;
}
LNZ[i]=l;
rt+=l+1;
int ll=i-l, rr=i+l+1;
ll--; rr++;
l=0, r=n;
while(r-l>1){
int mid = MID(l, r);
int a=ll-mid, b=rr+mid;
if(a<0||b>=n) { r=mid; continue; }
if(f1.get(a, ll-1)==f1.getrv(rr+1, b)&&f2.get(a, ll-1)==f2.getrv(rr+1, b)) l=mid;
else r=mid;
}
dp[ll][S[rr]-'a']+=l+1;
dp[rr][S[ll]-'a']+=l+1;
}
for(int i=0;i<n;i++){
int l=i-LNF[i], r=i+LNF[i];
if(l==r) continue;
PS[l]-=l; PS[i]+=l;
PS[i+1]+=r; PS[r+1]-=r;
PS[l]++; PS[i]--;
PS[i+1]++; PS[r+1]--;
T[l]++; T[i]--; T[i+1]--; T[r+1]++;
}
for(int i=0;i<n-1;i++) if(~LNZ[i]){
int l=i-LNZ[i], r=i+LNZ[i]+1;
PS[l]-=l; PS[i+1]+=l;
PS[i+1]+=r; PS[r+1]-=r;
PS[l]++; PS[i+1]--;
PS[i+1]++; PS[r+1]--;
T[l]++; T[i+1]--; T[i+1]--; T[r+1]++;
}
rtt=rt;
for(int i=1;i<N;i++) PS[i]+=PS[i-1];
for(int i=1;i<N;i++) T[i]+=T[i-1];
for(int i=0;i<n;i++) for(int j=0;j<L;j++){
rtt=max(rtt, rt+dp[i][j]-(PS[i]+1LL*T[i]*i));
}
printf("%lld", rtt);
}
Compilation message
palinilap.cpp: In function 'int32_t main()':
palinilap.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", S);
~~~~~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
14 ms |
5112 KB |
Output is correct |
| 3 |
Correct |
14 ms |
5112 KB |
Output is correct |
| 4 |
Correct |
14 ms |
5112 KB |
Output is correct |
| 5 |
Correct |
14 ms |
5112 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
24 ms |
6392 KB |
Output is correct |
| 2 |
Correct |
29 ms |
6264 KB |
Output is correct |
| 3 |
Correct |
32 ms |
6352 KB |
Output is correct |
| 4 |
Correct |
25 ms |
5852 KB |
Output is correct |
| 5 |
Correct |
30 ms |
6136 KB |
Output is correct |
| 6 |
Correct |
31 ms |
6392 KB |
Output is correct |
| 7 |
Correct |
30 ms |
6264 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
536 ms |
30224 KB |
Output is correct |
| 2 |
Incorrect |
426 ms |
30424 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
