Submission #996986

#	Time	Username	Problem	Language	Result	Execution time	Memory
996986		jpfr12	Palindromes (APIO14_palindrome)	C++17	0 / 100	1056 ms	6360 KiB

palindrome

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long int ull;
using namespace std;
const ll MOD = (ll)1e9+9;
int MAXN = 1e6;
 
//classes

 
 
//global
string str;
int n;
vector<ll> str_hash;
map<ll,ll> Map;
map<ll,int> Len;

void computeHash(){
  ll m = 1e9+9;
  ll p = 31;
  ll pow_p = 1;
  for(int i = 1; i <= n; i++){
    str_hash[i] = (str_hash[i-1] + (str[i-1] - 'a'+1)*pow_p)%m;
    pow_p = (pow_p*p)%m;
  }
}

void sol(int left, int right){
  while(left >= 0 && right < n){
    if(str[left] != str[right]) return;
    ll val = str_hash[right+1] - str_hash[left]*pow(31, right-left+1);
    val = (val%MOD +MOD)%MOD;
    Map[val]++;
    Len[val] = right-left+1;
    left--;
    right++;
  }
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  //ifstream fin("longpath.in");
  //ofstream fout("longpath.out");
  //stop
  cin >> str;
  n = str.length();
  str_hash.resize(n+1);
  computeHash();
  for(int i = 0; i < n; i++){
    sol(i, i);
    sol(i, i+1);
  }
  ll ans = 0LL;
  for(auto& i: Map){
    //cout << i.first << " " << i.second << '\n';
    ans = max(ans, i.second*Len[i.first]);
  }
  cout << ans << '\n';
  return 0;
} 

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