oj.uz

답안 #134987

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
134987 2019-07-23T13:48:02 Z fredbr 회문 (APIO14_palindrome) C++17
47 / 100
 961 ms 1536 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int const p = 117;
int const mod = 1e9 + 9;
int const maxn = 10010;

char s[maxn];
int h[maxn];
int pw[maxn];

vector<int> hs(int n) {
    vector<int> res(n+1);

    for (int i = 1; i <= n; i++) {
        res[i] = (ll(res[i-1])*p + s[i] ) % mod;
    }

    return res;
}

void init() {
    pw[0] = 1;
    for (int i = 1; i < maxn; i++)
        pw[i] = ll(pw[i-1])*p%mod;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    init();

    int n;

    string si;
    cin >> si;

    n = si.size();
    copy(si.begin(), si.end(), s+1);

    auto fh = hs(n);

    reverse(s+1, s+n+1);

    auto rh = hs(n);

    auto comp = [&] (int l, int r) -> pair<int, int> {
        int x = (ll(fh[r]) -     ll(fh[l-1])*pw[r-l+1]) % mod;
        int y = (ll(rh[n-l+1]) - ll(rh[n-r])*pw[r-l+1]) % mod;

        if (x < 0) x += mod;
        if (y < 0) y += mod;

        return {x == y, x};
    };

    ll ans = 0;

    vector<int> v;
    v.reserve(n);
    for (int lenght = 1; lenght <= n; lenght++) {
        v.clear();
        for (int l = 1; l + lenght - 1 <= n; l++) {
            int r = l + lenght - 1;

            auto x = comp(l, r);
            if (x.first) {
                v.push_back(x.second);
            }
        }

        sort(v.begin(), v.end());

        int best = 0;
        for (int i = 0; i < (int)v.size();) {
            int l = i;
            i++;
            while (i < (int)v.size() and (v[i] == v[i-1])) i++;
            best = max(best, i - l);
        }

        // cout << lenght << " " << best << "\n";
        ans = max(ans, ll(lenght)*best);

        // if (ll(best)*lenght >= ll(n-lenght+1)*(lenght+1)) break;
    }

    cout << ans << "\n";
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 380 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 2 ms 348 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 8 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 2 ms 376 KB Output is correct
30 Correct 2 ms 504 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Correct 2 ms 376 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 380 KB Output is correct
2 Correct 8 ms 376 KB Output is correct
3 Correct 11 ms 376 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 10 ms 376 KB Output is correct
6 Correct 10 ms 376 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 8 ms 376 KB Output is correct
9 Correct 6 ms 376 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 6 ms 376 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 697 ms 564 KB Output is correct
2 Correct 552 ms 504 KB Output is correct
3 Correct 961 ms 564 KB Output is correct
4 Correct 791 ms 508 KB Output is correct
5 Correct 370 ms 504 KB Output is correct
6 Correct 382 ms 632 KB Output is correct
7 Correct 438 ms 504 KB Output is correct
8 Correct 369 ms 504 KB Output is correct
9 Correct 368 ms 504 KB Output is correct
10 Correct 370 ms 504 KB Output is correct

Subtask #4
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 1536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -