#include <bits/stdc++.h>
#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )
#define int long long
using namespace std;
const int inf = (int)1e18 + 7;
const int N = (int)2e5 + 7;
int p = 997;
int dp[1002][1002];
int hs[N],pw[N];
int n,ans;
string a;
unordered_map<int,int> u;
void f (int l,int r) {
int lst= 0;
if (l > 0)
lst = hs[l - 1];
int o = hs[r] - lst;
o *= pw[n - l];
u[o] ++;
ans = max(ans,u[o] * (r - l + 1));
}
main () {
pw[0] = 1;
for (int i = 1; i <= 1010; i ++)
pw[i] = pw[i - 1] * p;
cin >> a;
n = a.size();
hs[0] = (int)(a[0] - 'a' + 1);
for (int i = 1; i < n; i ++)
hs[i] = hs[i - 1] + (pw[i] * (int)(a[i] - 'a' + 1));
for (int i = 0; i < n; i ++) {
for (int j = i; j >= 0; j --) {
if (i - j <= 1) {
if (a[i] == a[j]) {
dp[j][i] = 1;
f(j,i);
}
}
else if (dp[j + 1][i - 1]){
dp[j][i] = 1;
f(j,i);
}
}
}
cout << ans << endl;
}
Compilation message
palindrome.cpp:36:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main () {
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
2 |
Correct |
2 ms |
432 KB |
Output is correct |
3 |
Correct |
2 ms |
432 KB |
Output is correct |
4 |
Correct |
2 ms |
492 KB |
Output is correct |
5 |
Correct |
2 ms |
600 KB |
Output is correct |
6 |
Correct |
2 ms |
600 KB |
Output is correct |
7 |
Correct |
2 ms |
600 KB |
Output is correct |
8 |
Correct |
2 ms |
600 KB |
Output is correct |
9 |
Correct |
2 ms |
600 KB |
Output is correct |
10 |
Correct |
2 ms |
600 KB |
Output is correct |
11 |
Incorrect |
2 ms |
652 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
7480 KB |
Output is correct |
2 |
Correct |
60 ms |
13344 KB |
Output is correct |
3 |
Correct |
34 ms |
13344 KB |
Output is correct |
4 |
Correct |
115 ms |
19496 KB |
Output is correct |
5 |
Correct |
35 ms |
19496 KB |
Output is correct |
6 |
Correct |
33 ms |
19496 KB |
Output is correct |
7 |
Incorrect |
66 ms |
19496 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
26 ms |
19496 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
32 ms |
19496 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
169 ms |
44196 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |