oj.uz

답안 #867827

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
867827 2023-10-29T14:22:06 Z phongcd Palinilap (COI16_palinilap) C++14
0 / 100
 43 ms 23384 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long  double
#define ull unsigned long long
#define ii pair <int, int>
#define ill pair <ll, ll>
#define ild pair <ld, ld>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define file "test"
using namespace std;
const int N = 1e5 + 2;
const int M = 40;
const ll MOD = 1e9 + 7;
const ll INF = 3e18;
const ll base = 311;
const ll base2 = 1e4 + 7;
const int BLOCK_SIZE = 400;

int n;
ll pw[N], h[N];
ll f[N][26], bad[N];

ll get(int i, int j) {
    return (h[j] - h[i - 1] * pw[j - i + 1] + MOD * MOD) % MOD;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    string s; cin >> s;
    n = s.size();
    s = " " + s;

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

    ll sum = 0;
    for (int i = 1; i <= n; i ++) {
        int l = 0, r = min(i - 1, n - i);
        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if (get(i - mid, i) == get(i, i + mid)) 
                l = mid;
            else r = mid - 1;
        }
        
        sum += l + 1;
        for (int c = 0; c < 26; c ++) f[i][c] += l + 1;
        bad[i - l] ++, bad[i + l + 1] --;

        if (1 < i - l && i + l < n) {
            f[i - l - 1][s[i + l + 1] - 'a'] ++;
            f[i + l + 1][s[i - l - 1] - 'a'] ++;
        }

        int x = l, L = i - l - 2, R = i + l + 2;
        if (L < 1 || R > n) continue;

        l = 0, r = min(L - 1, n - R);
        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if (get(L - mid, L) == get(R, R + mid))
                l = mid;
            else r = mid - 1;
        }

        if (get(L - l, L) == get(R, R + l)) {
            f[i - x - 1][s[i + x + 1] - 'a'] += l + 1;
            f[i + x + 1][s[i - x - 1] - 'a'] += l + 1;
        }
    }

    for (int i = 1; i < n; i ++) {
        int l = 0, r = min(i - 1, n - i);
        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if (get(i - mid, i) == get(i + 1, i + 1 + mid)) 
                l = mid;
            else r = mid - 1;
        }

        if (get(i - l, i) == get(i + 1, i + 1 + l)) {
            sum += l + 1;
            bad[i - l] ++, bad[i + l + 2] --;
        }
        else l --;

        if (1 < i - l && i + l + 1 < n) {
            f[i - l - 1][s[i + l + 2] - 'a'] ++;
            f[i + l + 2][s[i - l - 1] - 'a'] ++;
        }

        int x = l, L = i - l - 2, R = i + l + 3;
        if (L < 1 || R > n) continue;

        l = 0, r = min(L - 1, n - R);
        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if (get(L - mid, L) == get(R, R + mid))
                l = mid;
            else r = mid - 1;
        }

        if (get(L - l, L) == get(R, R + l)) {
            f[i - x - 1][s[i + x + 2] - 'a'] += l + 1;
            f[i + x + 2][s[i - x - 1] - 'a'] += l + 1;
        }
    }

    ll ans = sum, cur = 0;
    for (int i = 1; i <= n; i ++) {
        cur += bad[i];
        for (int c = 0; c < 26; c ++)
            ans = max(ans, sum + f[i][c] - cur);
    }
    cout << ans;
}
/*
     /\_/\ zzZ
    (= -_-)
    / >u  >u
*/

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Incorrect 1 ms 2648 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 23384 KB Output isn't correct
2 Halted 0 ms 0 KB -