oj.uz

Submission #1082096

# Submission time Handle Problem Language Result Execution time Memory
1082096 2024-08-30T17:12:53 Z juicy Palinilap (COI16_palinilap) C++17
54 / 100
 36 ms 14680 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 = 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 0 ms 2648 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct

Subtask #2
37.0 / 37.0

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

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 14172 KB Output is correct
2 Correct 16 ms 14428 KB Output is correct
3 Correct 18 ms 14428 KB Output is correct
4 Correct 24 ms 14416 KB Output is correct
5 Correct 26 ms 14444 KB Output is correct
6 Correct 26 ms 14424 KB Output is correct
7 Correct 24 ms 14680 KB Output is correct
8 Correct 17 ms 6236 KB Output is correct
9 Correct 24 ms 14424 KB Output is correct
10 Correct 25 ms 14388 KB Output is correct
11 Correct 16 ms 14476 KB Output is correct
12 Correct 25 ms 14472 KB Output is correct
13 Correct 23 ms 14428 KB Output is correct
14 Correct 24 ms 14428 KB Output is correct
15 Correct 23 ms 14460 KB Output is correct
16 Incorrect 23 ms 14428 KB Output isn't correct
17 Halted 0 ms 0 KB -