Submission #47327

#	Time	Username	Problem	Language	Result	Execution time	Memory
47327		Talant	Palindromes (APIO14_palindrome)	C++17	0 / 100	356 ms	64524 KiB

palindrome

#include <bits/stdc++.h>

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )
#define int long long

using namespace std;

const int inf = (int)1e18 + 7;
const int N = (int)2e5 + 7;

int p = 97;
int dp[1002][1002];
int hs[N],pw[N];
int n,ans;

string a;
unordered_map<int,int> u;

void f (int l,int r) {
      int lst= 0;
      if (l > 0)
            lst = hs[l - 1];

      int o = hs[r] - lst;

      o *= pw[n - l];

      u[o] ++;
      ans = max(ans,u[o] * (r - l + 1));
}
main () {
      pw[0] = 1;
      for (int i = 1; i <= 1010; i ++)
            pw[i] = pw[i - 1] * p;

      cin >> a;

      n = a.size();

      hs[0] = (int)(a[0] - 'a' + 1);

      for (int i = 1; i < n; i ++)
            hs[i] = hs[i - 1] + (pw[i] * (int)(a[i] - 'a' + 1));

      for (int i = 0; i < n; i ++) {
            for (int j = i; j >= 0; j --) {
                  if (i - j <= 1) {
                        dp[j][i] = 1;
                        f(j,i);
                  }
                  else if (dp[j + 1][i - 1]){
                        dp[j][i] = 1;
                        f(j,i);
                  }
            }
      }
      cout << ans << endl;
}

Compilation message (stderr)

palindrome.cpp:36:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

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