# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
47989 | 2018-05-09T10:26:03 Z | Kmcode | Palindromes (APIO14_palindrome) | C++14 | 38 ms | 35196 KB |
#include "bits/stdc++.h" using namespace std; #define MAX 300015 char buf[MAX]; string s; int len[MAX]; int linkk[MAX]; int nex[MAX][26]; int ord; int cur; int cnt[MAX]; void append(int idx) { char c = s[idx]; while (!(idx-len[cur]-1>=0&&s[idx]==s[idx-len[cur]-1])) { cur = linkk[cur]; } if (nex[cur][c - 'a'] == -1) { nex[cur][c - 'a'] = ord; ord++; len[nex[cur][c - 'a']] = len[cur] + 2; linkk[nex[cur][c - 'a']] = linkk[cur]; cur = nex[cur][c - 'a']; if (len[cur] == 1) { linkk[cur] = 1; } else { while (nex[linkk[cur]][c - 'a'] == -1) { linkk[cur] = linkk[linkk[cur]]; } linkk[cur] = nex[linkk[cur]][c - 'a']; if (linkk[cur] <= 1)exit(1); } } cnt[cur]++; } int main() { memset(nex, -1,sizeof(nex) ); len[0] = -1; len[1] = 0; ord = 2; scanf("%s", buf); s = buf; linkk[1] = 0; linkk[0] = -1; for (int i = 0; i < s.size(); i++) { append(i); } long long int ans = 0; for (int i = ord - 1; i >= 2; i--) { cnt[linkk[i]] += cnt[i]; ans = max(ans, (long long int)(len[i])*cnt[i]); } printf("%lld\n", ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 24 ms | 30840 KB | Output is correct |
2 | Correct | 24 ms | 30948 KB | Output is correct |
3 | Correct | 26 ms | 30948 KB | Output is correct |
4 | Correct | 24 ms | 30948 KB | Output is correct |
5 | Correct | 24 ms | 31000 KB | Output is correct |
6 | Correct | 30 ms | 31176 KB | Output is correct |
7 | Correct | 24 ms | 31176 KB | Output is correct |
8 | Correct | 24 ms | 31176 KB | Output is correct |
9 | Correct | 24 ms | 31176 KB | Output is correct |
10 | Incorrect | 24 ms | 31176 KB | Output isn't correct |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 24 ms | 31176 KB | Output is correct |
2 | Correct | 24 ms | 31176 KB | Output is correct |
3 | Correct | 24 ms | 31176 KB | Output is correct |
4 | Correct | 24 ms | 31176 KB | Output is correct |
5 | Correct | 24 ms | 31176 KB | Output is correct |
6 | Correct | 24 ms | 31228 KB | Output is correct |
7 | Correct | 24 ms | 31228 KB | Output is correct |
8 | Correct | 24 ms | 31228 KB | Output is correct |
9 | Correct | 24 ms | 31228 KB | Output is correct |
10 | Incorrect | 24 ms | 31228 KB | Output isn't correct |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 25 ms | 31256 KB | Output is correct |
2 | Correct | 24 ms | 31256 KB | Output is correct |
3 | Correct | 24 ms | 31256 KB | Output is correct |
4 | Correct | 25 ms | 31256 KB | Output is correct |
5 | Correct | 25 ms | 31256 KB | Output is correct |
6 | Incorrect | 24 ms | 31256 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 28 ms | 32508 KB | Output is correct |
2 | Correct | 28 ms | 32508 KB | Output is correct |
3 | Correct | 27 ms | 32512 KB | Output is correct |
4 | Correct | 28 ms | 32512 KB | Output is correct |
5 | Correct | 28 ms | 32512 KB | Output is correct |
6 | Correct | 26 ms | 32512 KB | Output is correct |
7 | Correct | 27 ms | 32512 KB | Output is correct |
8 | Incorrect | 25 ms | 32512 KB | Output isn't correct |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 38 ms | 35196 KB | Output is correct |
2 | Incorrect | 33 ms | 35196 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |