oj.uz

Submission #538713

# Submission time Handle Problem Language Result Execution time Memory
538713 2022-03-17T15:07:55 Z radal Palindromes (APIO14_palindrome) C++17
100 / 100
 28 ms 35084 KB 
#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 3e5+20,mod = 1e9+7,inf = 1e9+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}

inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    }
    return z;
}
int tr[N][26],n,sz[N],cur,mx,suf[N],ans[N];
string s;
inline void add_to_tree(int i){
    while (i-sz[cur]-1 < 0 || s[i] != s[i-sz[cur]-1]){
        cur = suf[cur];
    }
    int c = s[i]-'a';
    if (!tr[cur][c]){
        mx++;
        tr[cur][c] = mx;
        sz[mx] = sz[cur]+2;
        int nxt = suf[cur];
        while (s[i] != s[i-sz[nxt]-1]) nxt = suf[nxt];
        if (sz[mx] > 1) suf[mx] = tr[nxt][c];
        else suf[mx] = 1;
        cur = mx;
        ans[mx]++;
    }
    else{
        cur = tr[cur][c];
        ans[cur]++;
    }
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> s;
    n = s.size();
    sz[0] = -1;
    sz[1] = 0;
    cur = 1;
    mx = 1;
    suf[1] = 0;
    suf[0] = 0;
    rep(i,0,n){
        add_to_tree(i);
    }
    ll ANS = 0;
    repr(i,mx,1){
        ans[suf[i]] += ans[i];
        ANS = max(ANS,1ll*ans[i]*sz[i]);
    }
    cout << ANS;
}

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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 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 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 328 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 1 ms 320 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 324 KB Output is correct
23 Correct 1 ms 324 KB Output is correct
24 Correct 1 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 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 456 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 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 1 ms 1488 KB Output is correct
2 Correct 2 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 1108 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11988 KB Output is correct
2 Correct 11 ms 11956 KB Output is correct
3 Correct 11 ms 11988 KB Output is correct
4 Correct 10 ms 11988 KB Output is correct
5 Correct 9 ms 12012 KB Output is correct
6 Correct 7 ms 8916 KB Output is correct
7 Correct 8 ms 10160 KB Output is correct
8 Correct 2 ms 692 KB Output is correct
9 Correct 4 ms 3296 KB Output is correct
10 Correct 8 ms 10196 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35036 KB Output is correct
2 Correct 26 ms 35056 KB Output is correct
3 Correct 28 ms 35024 KB Output is correct
4 Correct 27 ms 35084 KB Output is correct
5 Correct 26 ms 35060 KB Output is correct
6 Correct 23 ms 31216 KB Output is correct
7 Correct 22 ms 29256 KB Output is correct
8 Correct 6 ms 1240 KB Output is correct
9 Correct 5 ms 1240 KB Output is correct
10 Correct 22 ms 28776 KB Output is correct
11 Correct 25 ms 34992 KB Output is correct
12 Correct 8 ms 4316 KB Output is correct