oj.uz

Submission #535662

# Submission time Handle Problem Language Result Execution time Memory
535662 2022-03-10T20:46:16 Z getac Palindromes (APIO14_palindrome) C++14
100 / 100
 27 ms 36240 KB 
//InTheNameOfGOD
//PRS;)
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define rep(i, l, r) for(ll i = ll(l); i < ll(r); ++i)
#define per(i, l, r) for(ll i = ll(r) - 1; i >= ll(l); --i)
#define Fast cin.tie(0) -> sync_with_stdio(0);
#define min(x, y) (x < y ? x : y)
#define max(x, y) (x > y ? x : y)
typedef long long ll;
using namespace std;
constexpr int xn = 3e5 + 5;
int ng[xn][26], ans[xn], lk[xn], oc[xn], sz[xn], cnt, ti;
string s;
inline void ad(int v)
{
    while(s[v - sz[ti] - 1] != s[v]) ti = lk[ti];
    int x = lk[ti], c = s[v] - 'a';
    while(s[v - sz[x] - 1] != s[v]) x = lk[x];
    if(!ng[ti][c])
	{
        ng[ti][c] = ++cnt, sz[cnt] = sz[ti] + 2, lk[cnt] = sz[cnt] == 1 ? 2 : ng[x][c];
        ans[cnt] = ans[lk[cnt]] + 1;
    }
	ti = ng[ti][c], oc[ti]++;
}
int main()
{
	Fast
	cin >> s;
	int n = s.size();
	lk[1] = lk[2] = 1, cnt = ti = 2, sz[1] = -1, sz[2] = 0;
	rep(i, 0, n) ad(i);
	per(i, 1, cnt + 1) oc[lk[i]] += oc[i];
    ll ans = 0;
    rep(i, 2, cnt + 1) ans = max(ans, 1ll * oc[i] * sz[i]);
    cout << ans << '\n';
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Correct 0 ms 336 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 456 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 456 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1496 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1488 KB Output is correct
4 Correct 1 ms 1488 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 2 ms 1492 KB Output is correct
8 Correct 1 ms 472 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 1104 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12372 KB Output is correct
2 Correct 8 ms 12372 KB Output is correct
3 Correct 12 ms 12308 KB Output is correct
4 Correct 9 ms 12372 KB Output is correct
5 Correct 11 ms 12360 KB Output is correct
6 Correct 7 ms 9172 KB Output is correct
7 Correct 7 ms 10580 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 3 ms 3412 KB Output is correct
10 Correct 7 ms 10580 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 36176 KB Output is correct
2 Correct 22 ms 36180 KB Output is correct
3 Correct 23 ms 36160 KB Output is correct
4 Correct 23 ms 36188 KB Output is correct
5 Correct 27 ms 36152 KB Output is correct
6 Correct 25 ms 32220 KB Output is correct
7 Correct 23 ms 30292 KB Output is correct
8 Correct 5 ms 1200 KB Output is correct
9 Correct 5 ms 1228 KB Output is correct
10 Correct 20 ms 29760 KB Output is correct
11 Correct 23 ms 36240 KB Output is correct
12 Correct 6 ms 4444 KB Output is correct