#include <iostream>
using namespace std;
typedef long long ll;
string s;
int n, cnt1[100005], cnt2[100005];
ll frbr[100005], bcbr[100005], frsum[100005], bcsum[100005], b[100005], kolko[100005][30];
ll frh1[100005], frh2[100005], bch1[100005], bch2[100005], pot1[100005], pot2[100005];
const ll mod = (ll)1e9 + 7;
const ll B1 = 100003LL;
const ll B2 = 13337LL;
bool same(int prvix, int prviy, int drugix, int drugiy){
if((frh1[prviy] - (frh1[prvix - 1] * pot1[prviy - prvix + 1]) % mod + mod) % mod != (bch1[drugiy] - (bch1[drugix + 1] * pot1[drugix - drugiy + 1]) % mod + mod) % mod)
return 0;
if((frh2[prviy] - (frh2[prvix - 1] * pot2[prviy - prvix + 1]) % mod + mod) % mod != (bch2[drugiy] - (bch2[drugix + 1] * pot2[drugix - drugiy + 1]) % mod + mod) % mod)
return 0;
return 1;
}
ll brojpalin(){
ll ret = 0;
for(int i = 1 ; i <= n ; ++i){
int l = 0, r = min(i - 1, n - i);
while(l < r){
int mid = (l + r + 1) / 2;
if(same(i - mid, i - 1, i + mid, i + 1)){
l = mid;
}
else{
r = mid - 1;
}
}
ret += l + 1;
int x = i - l, y = i + l;
//cout << x << ' ' << i << " - " << y << ' ' << i << " : " << l << endl;
frbr[x]++;
frbr[i]--;
bcbr[y]++;
bcbr[i]--;
frsum[i] -= l;
bcsum[i] -= l;
x--;
y++;
if(x <= 0 || y > n)
continue;
int poc = l;
r = min(i - 1, n - i);
l = min(r, l + 1);
//cout << l << " - : - " << r << ".-." << poc << endl;
while(l < r){
int mid = (l + r + 1) / 2;
//cout << mid << "::" << same(i - mid, i - poc - 2, i + mid, i + poc + 2) << endl;
if(same(i - mid, i - poc - 2, i + mid, i + poc + 2)){
l = mid;
}
else{
r = mid - 1;
}
}
ll cnt = l - poc;
//cout << i << ' ' << l << ' ' << poc << endl;
kolko[x][s[y - 1] - 'a'] += cnt;
kolko[y][s[x - 1] - 'a'] += cnt;
}
for(int i = 1 ; i < n ; ++i){
int l = -1, r = min(i - 1, n - i - 1);
while(l < r){
int mid = (l + r + 1) / 2;
if(same(i - mid, i, i + mid + 1, i + 1)){
l = mid;
}
else{
r = mid - 1;
}
}
ret += l + 1;
int x = i - l, y = i + l + 1;
//cout << x << ' ' << i + 1 << " - " << y << ' ' << i << " : " << l << endl;
frbr[x]++;
frbr[i + 1]--;
bcbr[y]++;
bcbr[i]--;
frsum[i + 1] -= (l + 1);
bcsum[i] -= (l + 1);
x--;
y++;
if(x <= 0 || y > n)
continue;
int poc = l;
r = min(i - 1, n - i - 1);
l = min(r, l + 1);
while(l < r){
int mid = (l + r + 1) / 2;
if(same(i - mid, i - poc - 2, i + mid + 1, i + poc + 3)){
l = mid;
}
else{
r = mid - 1;
}
}
//cout << endl;
ll cnt = l - poc;
kolko[x][s[y - 1] - 'a'] += cnt;
kolko[y][s[x - 1] - 'a'] += cnt;
}
return ret;
}
void inithash(){
for(int i = 1 ; i <= n ; ++i){
frh1[i] = (frh1[i - 1] * B1 + s[i - 1] - 'a' + 1) % mod;
frh2[i] = (frh2[i - 1] * B2 + s[i - 1] - 'a' + 1) % mod;
}
for(int i = n ; i >= 1 ; --i){
bch1[i] = (bch1[i + 1] * B1 + s[i - 1] - 'a' + 1) % mod;
bch2[i] = (bch2[i + 1] * B2 + s[i - 1] - 'a' + 1) % mod;
}
pot1[0] = pot2[0] = 1;
for(int i = 1 ; i <= n ; ++i){
pot1[i] = (pot1[i - 1] * B1) % mod;
pot2[i] = (pot2[i - 1] * B2) % mod;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> s;
n = (int)s.size();
inithash();
ll sve = brojpalin();
ll sad = 0, cnt = 0;
for(int i = 1 ; i <= n ; ++i){
//cout << frbr[i] << ' ';
cnt += frbr[i];
sad += frsum[i];
sad += cnt;
b[i] += sad;
//cout << b[i] << ' ';
}
//cout << endl;
sad = 0;
cnt = 0;
for(int i = n ; i >= 1 ; --i){
cnt += bcbr[i];
sad += bcsum[i];
sad += cnt;
b[i] += sad;
}
/*
for(int i = 1 ; i <= n ; ++i){
cout << b[i] << ' ';
}
*/
ll sol = sve;
//cout << sol << endl;
for(int i = 1 ; i <= n ; ++i){
ll maxi = 0;
for(int j = 0 ; j < 26 ; ++j){
if(j == s[i - 1] - 'a')
continue;
maxi = max(maxi, (ll)kolko[i][j]);
}
sol = max(sol, sve - b[i] + maxi);
}
cout << sol << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
512 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
512 KB |
Output is correct |
| 5 |
Correct |
3 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
2048 KB |
Output is correct |
| 2 |
Correct |
7 ms |
2048 KB |
Output is correct |
| 3 |
Correct |
10 ms |
2048 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1380 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1792 KB |
Output is correct |
| 6 |
Correct |
3 ms |
2048 KB |
Output is correct |
| 7 |
Correct |
6 ms |
2048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
131 ms |
32796 KB |
Output is correct |
| 2 |
Correct |
193 ms |
32632 KB |
Output is correct |
| 3 |
Correct |
156 ms |
32632 KB |
Output is correct |
| 4 |
Correct |
145 ms |
32632 KB |
Output is correct |
| 5 |
Correct |
148 ms |
32692 KB |
Output is correct |
| 6 |
Correct |
149 ms |
32652 KB |
Output is correct |
| 7 |
Correct |
152 ms |
32864 KB |
Output is correct |
| 8 |
Correct |
112 ms |
9244 KB |
Output is correct |
| 9 |
Correct |
148 ms |
32836 KB |
Output is correct |
| 10 |
Correct |
138 ms |
32632 KB |
Output is correct |
| 11 |
Correct |
182 ms |
32632 KB |
Output is correct |
| 12 |
Correct |
132 ms |
32632 KB |
Output is correct |
| 13 |
Correct |
175 ms |
32616 KB |
Output is correct |
| 14 |
Correct |
145 ms |
32668 KB |
Output is correct |
| 15 |
Correct |
138 ms |
32632 KB |
Output is correct |
| 16 |
Correct |
197 ms |
32620 KB |
Output is correct |
| 17 |
Correct |
134 ms |
32760 KB |
Output is correct |
| 18 |
Correct |
172 ms |
32732 KB |
Output is correct |
| 19 |
Correct |
121 ms |
32760 KB |
Output is correct |
