#include <iostream>
using namespace std;
typedef long long ll;
string s;
int n, cnt1[100005], cnt2[100005], kolko[100005][30];
ll frbr[100005], bcbr[100005], frsum[100005], bcsum[100005], b[100005];
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;
}
}
int 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;
int 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 |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1408 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1300 KB |
Output is correct |
| 3 |
Correct |
7 ms |
1408 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1024 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1280 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1408 KB |
Output is correct |
| 7 |
Correct |
7 ms |
1408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
113 ms |
20984 KB |
Output is correct |
| 2 |
Correct |
128 ms |
21008 KB |
Output is correct |
| 3 |
Correct |
124 ms |
21052 KB |
Output is correct |
| 4 |
Correct |
105 ms |
21116 KB |
Output is correct |
| 5 |
Correct |
100 ms |
21060 KB |
Output is correct |
| 6 |
Correct |
136 ms |
20984 KB |
Output is correct |
| 7 |
Correct |
130 ms |
21048 KB |
Output is correct |
| 8 |
Correct |
110 ms |
9328 KB |
Output is correct |
| 9 |
Correct |
147 ms |
21080 KB |
Output is correct |
| 10 |
Correct |
111 ms |
20984 KB |
Output is correct |
| 11 |
Correct |
144 ms |
21040 KB |
Output is correct |
| 12 |
Correct |
152 ms |
21112 KB |
Output is correct |
| 13 |
Correct |
122 ms |
20956 KB |
Output is correct |
| 14 |
Correct |
158 ms |
20956 KB |
Output is correct |
| 15 |
Correct |
140 ms |
20956 KB |
Output is correct |
| 16 |
Incorrect |
181 ms |
21112 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
