Submission #997405

#	Time	Username	Problem	Language	Result	Execution time	Memory
997405		vjudge1	Palindromes (APIO14_palindrome)	C++17	8 / 100	1088 ms	16020 KiB

palindrome

#include<bits/stdc++.h>

using namespace std;

const int N = 3e5+5, base = 727, mod = 998244353;
map<int,int> cnt[N];
string s;

void update(int l, int r) // l and r are inclusive
{
  // [l + 1, ...., r - 1]
  int hsh = 0;
  for(int i = l; i <= r; i++)
    hsh = (1ll * hsh * base % mod + s[i]) % mod;
  
  cnt[(r - l + 1) / 2][hsh]++;
}

int main()
{
  cin >> s;
  int len = s.size();
  string t;

  t = "#";
  for(char i : s) {
    t += i; t += '#';
  }
  s = t;
  int n = s.size();
  for(int c = 0; c < n; c++)
    {
      if(c != '#')
	update(c, c);
      int l = c - 1, r = c + 1;
      while(l >= 0 && r < s.size() && s[l] == s[r])
	{
	  if(s[l] == '#')
	    update(l, r);
	  l--, r++;
	}
    }

  
  long long ans = 0;
  for(int i = 1; i <= len; i ++)
    {
      int mx = 0;
      for(auto x : cnt[i])
	mx = max(mx, x.second);
      ans = max(ans, 1ll * mx * i);
    }
  cout << ans << endl;
  return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:36:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |       while(l >= 0 && r < s.size() && s[l] == s[r])
      |                       ~~^~~~~~~~~~

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