oj.uz

Submission #1082097

# Submission time Handle Problem Language Result Execution time Memory
1082097 2024-08-30T17:13:21 Z juicy Palinilap (COI16_palinilap) C++17
54 / 100
 35 ms 14376 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
using ull = unsigned long long;
 
const int N = 1e5 + 5;
 
int n;
int cnt[N];
long long f[N];
array<int, 26> c[N];
string s;
ull h[N], rh[N], pw[N];
 
ull qry(int l, int r, ull *h) {
  return h[r] - h[l - 1] * pw[r - l + 1];
}
 
int find(int s, int e) {
  if (s < 1 || e > n) {
    return 0;
  }
  int l = 0, r = min(s, n - e + 1), res = 0;
  while (l <= r) {
    int m = (l + r) / 2;
    if (qry(s - m + 1, s, h) == qry(n - e - m + 2, n - e + 1, rh)) {
      res = m;
      l = m + 1;
    } else {
      r = m - 1;
    }
  }
  return res;
}
 
template<class T>
void upd(int s, int e, int x, T *f) {
  f[s] += x;
  f[e + 1] -= x; 
}
 
int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
 
  cin >> s;
  n = s.size();
  pw[0] = 1;
  for (int i = 0; i < n; ++i) {
    pw[i + 1] = pw[i] * 31;
    h[i + 1] = h[i] * 31 + s[i] - 'a' + 1;
  }
  for (int i = n - 1; i >= 0; --i) {
    rh[i + 1] = rh[i + 2] * 31 + s[i] - 'a' + 1;
  }
  reverse(rh + 1, rh + n + 1);
  long long res = 0;
  for (int i = 1; i < n; ++i) {
    int l = find(i, i + 1);
    res += l;
    int L = i - l + 1, R = i + l;
    if (l > 0) {
      upd(i + 1, i + l, 1, cnt);
      upd(i + 1, i + l, -R - 1, f);
      upd(i - l + 1, i, -1, cnt);
      upd(i - l + 1, i, L - 1, f);
    }
    if (1 < L && R < n) {
      int l = find(L - 2, R + 2);
      c[L - 1][s[R] - 'a'] += l + 1;
      c[R + 1][s[L - 2] - 'a'] += l + 1;
    }
  }
  for (int i = 1; i <= n; ++i) {
    int l = find(i - 1, i + 1) + 1;
    res += l;
    int L = i - l + 1, R = i + l - 1;
    if (l > 1) {
      upd(L, i - 1, -1, cnt);
      upd(L, i - 1, L - 1, f);
      upd(i + 1, R, 1, cnt);
      upd(i + 1, R, -R - 1, f);
    }
    if (1 < L && R < n) {
      int l = find(L - 2, R + 2);
      c[L - 1][s[R] - 'a'] += l + 1;
      c[R + 1][s[L - 2] - 'a'] += l + 1;
    }
  }
  long long ma = 0;
  for (int i = 1; i <= n; ++i) {
    cnt[i] += cnt[i - 1];
    f[i] += f[i - 1];
    long long delta = (long long) cnt[i] * i + f[i];
    for (int j = 0; j < 26; ++j) {
      ma = max(ma, delta + c[i][j]);
    }
  }
  cout << res + ma;
  return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 14304 KB Output is correct
2 Correct 19 ms 14168 KB Output is correct
3 Correct 18 ms 14172 KB Output is correct
4 Correct 25 ms 14204 KB Output is correct
5 Correct 27 ms 14172 KB Output is correct
6 Correct 24 ms 14172 KB Output is correct
7 Correct 33 ms 14172 KB Output is correct
8 Correct 18 ms 6128 KB Output is correct
9 Correct 24 ms 14376 KB Output is correct
10 Correct 24 ms 14348 KB Output is correct
11 Correct 18 ms 14172 KB Output is correct
12 Correct 35 ms 14296 KB Output is correct
13 Correct 23 ms 14168 KB Output is correct
14 Correct 28 ms 14144 KB Output is correct
15 Correct 27 ms 14168 KB Output is correct
16 Incorrect 26 ms 14172 KB Output isn't correct
17 Halted 0 ms 0 KB -