Submission #1082105

#TimeUsernameProblemLanguageResultExecution timeMemory
1082105juicyPalinilap (COI16_palinilap)C++17
54 / 100
33 ms24652 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif using ull = unsigned long long; const int N = 1e5 + 5; int n; int cnt[N]; long long f[N]; array<long long, 26> c[N]; string s; ull h[N], rh[N], pw[N]; ull qry(int l, int r, ull *h) { return h[r] - h[l - 1] * pw[r - l + 1]; } int find(int s, int e) { if (s < 1 || e > n) { return 0; } int l = 0, r = min(s, n - e + 1), res = 0; while (l <= r) { int m = (l + r) / 2; if (qry(s - m + 1, s, h) == qry(n - e - m + 2, n - e + 1, rh)) { res = m; l = m + 1; } else { r = m - 1; } } return res; } template<class T> void upd(int s, int e, int x, T *f) { f[s] += x; f[e + 1] -= x; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> s; n = s.size(); pw[0] = 1; for (int i = 0; i < n; ++i) { pw[i + 1] = pw[i] * 31; h[i + 1] = h[i] * 31 + s[i] - 'a' + 1; } for (int i = n - 1; i >= 0; --i) { rh[i + 1] = rh[i + 2] * 31 + s[i] - 'a' + 1; } reverse(rh + 1, rh + n + 1); long long res = 0; for (int i = 1; i < n; ++i) { int l = find(i, i + 1); res += l; int L = i - l + 1, R = i + l; if (l > 0) { upd(i + 1, i + l, 1, cnt); upd(i + 1, i + l, -R - 1, f); upd(i - l + 1, i, -1, cnt); upd(i - l + 1, i, L - 1, f); } if (1 < L && R < n) { int l = find(L - 2, R + 2); c[L - 1][s[R] - 'a'] += l + 1; c[R + 1][s[L - 2] - 'a'] += l + 1; } } for (int i = 1; i <= n; ++i) { int l = find(i - 1, i + 1) + 1; res += l; int L = i - l + 1, R = i + l - 1; if (l > 1) { upd(L, i - 1, -1, cnt); upd(L, i - 1, L - 1, f); upd(i + 1, R, 1, cnt); upd(i + 1, R, -R - 1, f); } if (1 < L && R < n) { int l = find(L - 2, R + 2); c[L - 1][s[R] - 'a'] += l + 1; c[R + 1][s[L - 2] - 'a'] += l + 1; } } long long ma = 0; for (int i = 1; i <= n; ++i) { cnt[i] += cnt[i - 1]; f[i] += f[i - 1]; long long delta = (long long) cnt[i] * i + f[i]; for (int j = 0; j < 26; ++j) { ma = max(ma, delta + c[i][j]); } } cout << res + ma; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...