# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
47990 | 2018-05-09T10:29:23 Z | Kmcode | Palindromes (APIO14_palindrome) | C++14 | 50 ms | 35508 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);}}else {cur = nex[cur][c - 'a'];}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 | 30956 KB | Output is correct |
3 | Correct | 23 ms | 31140 KB | Output is correct |
4 | Correct | 26 ms | 31140 KB | Output is correct |
5 | Correct | 24 ms | 31140 KB | Output is correct |
6 | Correct | 24 ms | 31140 KB | Output is correct |
7 | Correct | 24 ms | 31168 KB | Output is correct |
8 | Correct | 24 ms | 31168 KB | Output is correct |
9 | Correct | 24 ms | 31168 KB | Output is correct |
10 | Incorrect | 27 ms | 31196 KB | Output isn't correct |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 24 ms | 31196 KB | Output is correct |
2 | Correct | 24 ms | 31196 KB | Output is correct |
3 | Correct | 24 ms | 31196 KB | Output is correct |
4 | Correct | 26 ms | 31196 KB | Output is correct |
5 | Correct | 24 ms | 31196 KB | Output is correct |
6 | Correct | 24 ms | 31196 KB | Output is correct |
7 | Correct | 24 ms | 31196 KB | Output is correct |
8 | Correct | 24 ms | 31196 KB | Output is correct |
9 | Correct | 24 ms | 31196 KB | Output is correct |
10 | Correct | 24 ms | 31196 KB | Output is correct |
11 | Correct | 29 ms | 31196 KB | Output is correct |
12 | Incorrect | 24 ms | 31196 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 30 ms | 31228 KB | Output is correct |
2 | Correct | 24 ms | 31228 KB | Output is correct |
3 | Correct | 25 ms | 31228 KB | Output is correct |
4 | Correct | 24 ms | 31228 KB | Output is correct |
5 | Correct | 26 ms | 31228 KB | Output is correct |
6 | Correct | 26 ms | 31228 KB | Output is correct |
7 | Correct | 24 ms | 31272 KB | Output is correct |
8 | Correct | 24 ms | 31272 KB | Output is correct |
9 | Correct | 24 ms | 31272 KB | Output is correct |
10 | Incorrect | 31 ms | 31272 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 27 ms | 32580 KB | Output is correct |
2 | Correct | 27 ms | 32580 KB | Output is correct |
3 | Correct | 28 ms | 32580 KB | Output is correct |
4 | Correct | 27 ms | 32580 KB | Output is correct |
5 | Correct | 28 ms | 32580 KB | Output is correct |
6 | Correct | 30 ms | 32580 KB | Output is correct |
7 | Correct | 29 ms | 32580 KB | Output is correct |
8 | Correct | 28 ms | 32580 KB | Output is correct |
9 | Correct | 50 ms | 32580 KB | Output is correct |
10 | Incorrect | 28 ms | 32580 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 36 ms | 35488 KB | Output is correct |
2 | Correct | 35 ms | 35488 KB | Output is correct |
3 | Correct | 34 ms | 35488 KB | Output is correct |
4 | Correct | 36 ms | 35488 KB | Output is correct |
5 | Correct | 37 ms | 35488 KB | Output is correct |
6 | Correct | 35 ms | 35488 KB | Output is correct |
7 | Correct | 35 ms | 35488 KB | Output is correct |
8 | Correct | 29 ms | 35488 KB | Output is correct |
9 | Correct | 31 ms | 35488 KB | Output is correct |
10 | Incorrect | 35 ms | 35508 KB | Output isn't correct |
11 | Halted | 0 ms | 0 KB | - |