Submission #104889

#TimeUsernameProblemLanguageResultExecution timeMemory
104889ShtefPalinilap (COI16_palinilap)C++14
54 / 100
181 ms21116 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...