# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
114205 | 2019-05-31T09:35:26 Z | patrikpavic2 | Palindromes (APIO14_palindrome) | C++17 | 158 ms | 83132 KB |
#include <algorithm> #include <vector> #include <cstdio> #include <cstring> #define PB push_back using namespace std; typedef long long ll; const int N = 3e5 + 500; const int INF = 0x3f3f3f3f; struct node{ node* CH[30]; node* bk; int len, cnt; } *n0, *n1; bool cmp(node* X, node* Y){ return X -> len > Y -> len; } char s[N]; int n; ll mx; vector < node* > v; void precompute(){ n1 = new node(); n0 = new node(); n1 -> len = -1, n0 -> len = 0; n0 -> bk = n1; n1 -> bk = n1; node* cur = n0; for(int i = 0;i < n;i++){ for(; cur->len + 1 > i || s[i - cur->len - 1] != s[i]; cur = cur -> bk); node *rmb = cur -> bk; if(cur -> CH[s[i] - 'a'] == NULL) cur -> CH[s[i] - 'a'] = new node(), v.PB(cur -> CH[s[i] - 'a']); cur -> CH[s[i] - 'a'] -> len = cur -> len + 2; cur = cur -> CH[s[i] - 'a']; cur -> cnt++; //printf("len = %d\n", cur -> len); for(; rmb -> len + 1 > i || s[i - rmb->len - 1] != s[i]; rmb = rmb -> bk); if(cur -> len == 1) cur -> bk = n0; else{ if(rmb -> CH[s[i] - 'a'] == NULL) rmb -> CH[s[i] - 'a'] = new node(), v.PB(rmb -> CH[s[i] - 'a']); cur -> bk = rmb -> CH[s[i] - 'a']; } //printf("bk = %d\n", cur -> bk -> len); } } int main(){ scanf("%s", s); n = strlen(s); precompute(); sort(v.begin(), v.end(), cmp); for(int i = 0;i < v.size();i++){ mx = max(mx, (ll)v[i] -> len * v[i] -> cnt); v[i] -> bk -> cnt += v[i] -> cnt; } printf("%lld\n", mx); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 384 KB | Output is correct |
3 | Correct | 2 ms | 256 KB | Output is correct |
4 | Correct | 2 ms | 256 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
6 | Correct | 2 ms | 384 KB | Output is correct |
7 | Correct | 2 ms | 256 KB | Output is correct |
8 | Correct | 2 ms | 256 KB | Output is correct |
9 | Correct | 2 ms | 256 KB | Output is correct |
10 | Correct | 2 ms | 384 KB | Output is correct |
11 | Correct | 2 ms | 384 KB | Output is correct |
12 | Correct | 2 ms | 256 KB | Output is correct |
13 | Correct | 2 ms | 384 KB | Output is correct |
14 | Correct | 2 ms | 384 KB | Output is correct |
15 | Correct | 2 ms | 256 KB | Output is correct |
16 | Correct | 2 ms | 384 KB | Output is correct |
17 | Correct | 2 ms | 256 KB | Output is correct |
18 | Correct | 2 ms | 256 KB | Output is correct |
19 | Correct | 2 ms | 384 KB | Output is correct |
20 | Correct | 2 ms | 384 KB | Output is correct |
21 | Correct | 1 ms | 256 KB | Output is correct |
22 | Correct | 1 ms | 256 KB | Output is correct |
23 | Correct | 2 ms | 256 KB | Output is correct |
24 | Correct | 2 ms | 384 KB | Output is correct |
25 | Correct | 2 ms | 256 KB | Output is correct |
26 | Correct | 2 ms | 384 KB | Output is correct |
27 | Correct | 2 ms | 256 KB | Output is correct |
28 | Correct | 2 ms | 384 KB | Output is correct |
29 | Correct | 2 ms | 384 KB | Output is correct |
30 | Correct | 1 ms | 256 KB | Output is correct |
31 | Correct | 2 ms | 256 KB | Output is correct |
32 | Correct | 2 ms | 256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 512 KB | Output is correct |
2 | Correct | 2 ms | 512 KB | Output is correct |
3 | Correct | 2 ms | 640 KB | Output is correct |
4 | Correct | 2 ms | 512 KB | Output is correct |
5 | Correct | 2 ms | 512 KB | Output is correct |
6 | Correct | 2 ms | 512 KB | Output is correct |
7 | Correct | 2 ms | 640 KB | Output is correct |
8 | Correct | 2 ms | 640 KB | Output is correct |
9 | Correct | 2 ms | 512 KB | Output is correct |
10 | Correct | 2 ms | 384 KB | Output is correct |
11 | Correct | 4 ms | 384 KB | Output is correct |
12 | Correct | 5 ms | 512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 3072 KB | Output is correct |
2 | Correct | 5 ms | 3072 KB | Output is correct |
3 | Correct | 5 ms | 3072 KB | Output is correct |
4 | Correct | 5 ms | 3072 KB | Output is correct |
5 | Correct | 5 ms | 3072 KB | Output is correct |
6 | Correct | 5 ms | 3072 KB | Output is correct |
7 | Correct | 5 ms | 3072 KB | Output is correct |
8 | Correct | 2 ms | 384 KB | Output is correct |
9 | Correct | 2 ms | 384 KB | Output is correct |
10 | Correct | 4 ms | 2176 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 44 ms | 27920 KB | Output is correct |
2 | Correct | 55 ms | 27844 KB | Output is correct |
3 | Correct | 40 ms | 28012 KB | Output is correct |
4 | Correct | 48 ms | 28012 KB | Output is correct |
5 | Correct | 54 ms | 27884 KB | Output is correct |
6 | Correct | 31 ms | 20460 KB | Output is correct |
7 | Correct | 34 ms | 23660 KB | Output is correct |
8 | Correct | 4 ms | 768 KB | Output is correct |
9 | Correct | 10 ms | 6908 KB | Output is correct |
10 | Correct | 39 ms | 23656 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 111 ms | 83040 KB | Output is correct |
2 | Correct | 134 ms | 83052 KB | Output is correct |
3 | Correct | 113 ms | 83132 KB | Output is correct |
4 | Correct | 148 ms | 83020 KB | Output is correct |
5 | Correct | 158 ms | 83080 KB | Output is correct |
6 | Correct | 125 ms | 74724 KB | Output is correct |
7 | Correct | 115 ms | 69276 KB | Output is correct |
8 | Correct | 7 ms | 1348 KB | Output is correct |
9 | Correct | 6 ms | 1280 KB | Output is correct |
10 | Correct | 135 ms | 68196 KB | Output is correct |
11 | Correct | 112 ms | 83040 KB | Output is correct |
12 | Correct | 14 ms | 8828 KB | Output is correct |