Submission #1097610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097610		duckindog	Palindromes (APIO14_palindrome)	C++17	8 / 100	1075 ms	20184 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

const int N = 300'000 + 10;
string s;
int n;

using ull = unsigned long long;
const int base = 19937;
ull h[N], rh[N], pw[N];
void initHash() { 
  pw[0] = 1;
  for (int i = 1; i <= n; ++i) { 
    h[i] = h[i - 1] * base + s[i];
    pw[i] = pw[i - 1] * base;
  }
  reverse(s.begin() + 1, s.end());
  for (int i = 1; i <= n; ++i) rh[i] = rh[i - 1] * base + s[i];
  reverse(s.begin() + 1, s.end());
}
ull get(int l, int r) { return h[r] - h[l - 1] * pw[r - l + 1]; }
ull rget(int l, int r) { 
  tie(l, r) = make_pair(n - r + 1, n - l + 1);
  return rh[r] - rh[l - 1] * pw[r - l + 1];
}
bool chk(int l, int r) { return get(l, r) == rget(l, r); }

unordered_map<ull, long long> cnt;

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> s;
  n = s.size(); s = '@' + s;
  
  initHash();
  for (int i = 1; i <= n; ++i) { 
    for (int j = i; j <= n; ++j) if (chk(i, j)) cnt[get(i, j)] += j - i + 1;
  }

  long long answer = 0;
  for (const auto& x : cnt) answer = max(answer, x.second);

  cout << answer << "\n";
  cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27