Submission #47334

#	Time	Username	Problem	Language	Result	Execution time	Memory
47334		mirbek01	Palindromes (APIO14_palindrome)	C++17	0 / 100	1076 ms	1952 KiB

palindrome

# include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 2;

string s;
int n;
long long ans, h[N], pw[N], pr = 997, mod = 1e9 + 7;
map < pair <int, int> , int> mp;

int get(int l, int r){
      long long hs = h[r] - h[l - 1];
      hs *= pw[N - l];
      return hs;
}

bool ispal(int l, int r){
      return get(l, r) == get(n - r + 1, n - l + 1);
}

int main(){
      pw[0] = pr;

      for(int i = 1; i < N; i ++)
            pw[i] = pw[i - 1] * pr;

      cin >> s;
      n = s.size();
      s = ' ' + s;

      for(int i = 1; i <= n; i ++){
            h[i] = h[i - 1] + s[i] * pw[i];
      }

      for(int i = 1; i <= n; i ++){
            for(int j = i; j <= n; j ++){
                  if(ispal(i, j)){
                        mp[{j - i + 1, get(i, j)}] ++;
                  }
            }
      }

      for(auto i : mp){
            long long cur = i.first.first * i.second;
            ans = max(ans, cur);
      }

      cout << ans << endl;
}

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