Submission #239765

#	Time	Username	Problem	Language	Result	Execution time	Memory
239765		neihcr7j	Palindromes (APIO14_palindrome)	C++14	47 / 100	1094 ms	7808 KiB

palindrome

#include<bits/stdc++.h>

#define M 1000000013
#define maxn 300005

using namespace std;
typedef long long ll;

ll mul(ll a, ll b) {
  return a * b % M;
}

ll norm(ll a) {
  return (a < 0 ? a + M : a >= M ? a - M : a);
}

char a[maxn];
ll h[maxn], ih[maxn];
ll p[maxn];

int get(ll h[], int l, int r) {
  return norm(h[r] - mul(h[l - 1], p[r - l + 1]));
}

int main(){
  #define TASK "ABC"
  //freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout);
  ios_base::sync_with_stdio(0);

  cin >> a + 1;
  int n = strlen(a + 1);

  p[0] = 1;
  for (int i = 1; i <= n; ++i)
    p[i] = mul(p[i - 1], 26);

  h[0] = 0;
  for (int i = 1; i <= n; ++i)
    h[i] = norm(mul(h[i - 1], 26) + a[i]);

  ih[0] = 0;
  for (int i = 1; i <= n; ++i)
    ih[i] = norm(mul(ih[i - 1], 26) + a[n - i + 1]);

  ll ans = 0;
  for (int len = 0; len < n; ++len) {
    map < ll, ll > mp;
    for (int i = 1; i + len <= n; ++i) {
      ll ret = get(h, i, i + len);
      if (ret != get(ih, n + 1 - i - len, n + 1 - i)) continue;
      ans = max(ans, (++mp[ret]) * (len + 1));
    }
  }

  cout << ans << '\n';
  return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:30:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   cin >> a + 1;
          ~~^~~

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