oj.uz

Submission #107954

# Submission time Handle Problem Language Result Execution time Memory
107954 2019-04-26T10:07:22 Z SamAnd Palindromes (APIO14_palindrome) C++17
23 / 100
 705 ms 132096 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 10004;
const long long P = 31;

int n;
char aa[N], a[N];

long long ast[N];
long long p[N], s[N];

bool pal(int l, int r)
{
    return (p[r] - p[l - 1]) * ast[n - r] == (s[l] - s[r + 1]) * ast[l - 1];
}

int z;
map<int, int> t[N * 200];
int b[N * 200];

int main()
{
    cin >> aa;
    n = strlen(aa);
    for (int i = 1; i <= n; ++i)
        a[i] = aa[i - 1];

    ast[0] = 1;
    for (int i = 1; i <= n; ++i)
        ast[i] = ast[i - 1] * P;

    for (int i = 1; i <= n; ++i)
        p[i] = p[i - 1] + ast[i - 1] * (a[i] - 'a' + 1);
    for (int i = n; i >= 1; --i)
        s[i] = s[i + 1] + ast[n - i] * (a[i] - 'a' + 1);

    for (int l = 1; l <= n; ++l)
    {
        int pos = 0;
        for (int r = l; r <= n; ++r)
        {
            if (t[pos].find(a[r] - 'a') == t[pos].end())
                t[pos][a[r] - 'a'] = ++z;
            pos = t[pos][a[r] - 'a'];
            b[pos]++;
        }
    }

    int ans = 0;
    for (int l = 1; l <= n; ++l)
    {
        int pos = 0;
        for (int r = l; r <= n; ++r)
        {
            pos = t[pos][a[r] - 'a'];
            if (pal(l, r))
                ans = max(ans, b[pos] * (r - l + 1));
        }
    }

    cout << ans << endl;
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 94328 KB Output is correct
2 Correct 84 ms 94328 KB Output is correct
3 Correct 91 ms 94456 KB Output is correct
4 Correct 87 ms 94256 KB Output is correct
5 Correct 98 ms 94364 KB Output is correct
6 Correct 90 ms 94300 KB Output is correct
7 Correct 103 ms 94252 KB Output is correct
8 Correct 87 ms 94332 KB Output is correct
9 Correct 86 ms 94328 KB Output is correct
10 Correct 87 ms 94328 KB Output is correct
11 Correct 90 ms 94328 KB Output is correct
12 Correct 87 ms 94328 KB Output is correct
13 Correct 86 ms 94460 KB Output is correct
14 Correct 84 ms 94456 KB Output is correct
15 Correct 86 ms 94248 KB Output is correct
16 Correct 87 ms 94328 KB Output is correct
17 Correct 124 ms 94328 KB Output is correct
18 Correct 91 ms 94328 KB Output is correct
19 Correct 87 ms 94332 KB Output is correct
20 Correct 89 ms 94328 KB Output is correct
21 Correct 103 ms 94424 KB Output is correct
22 Correct 87 ms 94648 KB Output is correct
23 Correct 104 ms 94328 KB Output is correct
24 Correct 100 ms 94476 KB Output is correct
25 Correct 83 ms 94332 KB Output is correct
26 Correct 89 ms 94584 KB Output is correct
27 Correct 88 ms 94456 KB Output is correct
28 Correct 82 ms 94544 KB Output is correct
29 Correct 83 ms 94456 KB Output is correct
30 Correct 85 ms 94584 KB Output is correct
31 Correct 88 ms 94584 KB Output is correct
32 Correct 91 ms 94460 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 94680 KB Output is correct
2 Correct 133 ms 107940 KB Output is correct
3 Correct 97 ms 94360 KB Output is correct
4 Correct 189 ms 116984 KB Output is correct
5 Correct 96 ms 94328 KB Output is correct
6 Correct 93 ms 94324 KB Output is correct
7 Correct 131 ms 111480 KB Output is correct
8 Correct 103 ms 94456 KB Output is correct
9 Correct 168 ms 117880 KB Output is correct
10 Correct 160 ms 119608 KB Output is correct
11 Correct 176 ms 119544 KB Output is correct
12 Correct 139 ms 113656 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 705 ms 95608 KB Output is correct
2 Runtime error 151 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 243 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 225 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -