oj.uz

Submission #137288

# Submission time Handle Problem Language Result Execution time Memory
137288 2019-07-27T12:19:51 Z egorlifar Palindromes (APIO14_palindrome) C++17
100 / 100
 169 ms 83308 KB 
/*
ЗАПУСКАЕМ
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
 
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left224
#define right right224
#define next next224
#define rank rank224
#define prev prev224
#define y1 y1224
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define mp make_pair
const string FILENAME = "input";
using ll = long long;
 

struct node{
    node* CH[30];
    node* bk;
    int len, cnt;
} *n0, *n1;
 

bool cmp(node* X, node* Y){
    return X -> len > Y -> len;
}
 
int n;
string s;
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++;
        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'];
        }
    }
}
 
 
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //read(FILENAME); 
    cin >> s;
    n = sz(s);
    precompute();
    sort(all(v), cmp);
    for (auto &x: v) {
        chkmax(mx, (ll)x -> len * x -> cnt);
        x -> bk -> cnt += x -> cnt;
    }
    cout << mx << endl;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 636 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 504 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3192 KB Output is correct
2 Correct 6 ms 3072 KB Output is correct
3 Correct 5 ms 3064 KB Output is correct
4 Correct 6 ms 3064 KB Output is correct
5 Correct 6 ms 3064 KB Output is correct
6 Correct 6 ms 3064 KB Output is correct
7 Correct 6 ms 3064 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 5 ms 2296 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 28012 KB Output is correct
2 Correct 53 ms 28016 KB Output is correct
3 Correct 41 ms 27988 KB Output is correct
4 Correct 53 ms 28024 KB Output is correct
5 Correct 52 ms 28016 KB Output is correct
6 Correct 34 ms 20592 KB Output is correct
7 Correct 38 ms 23916 KB Output is correct
8 Correct 5 ms 808 KB Output is correct
9 Correct 13 ms 6904 KB Output is correct
10 Correct 42 ms 23792 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 83308 KB Output is correct
2 Correct 149 ms 83184 KB Output is correct
3 Correct 135 ms 83188 KB Output is correct
4 Correct 166 ms 83308 KB Output is correct
5 Correct 169 ms 83092 KB Output is correct
6 Correct 135 ms 74872 KB Output is correct
7 Correct 125 ms 69344 KB Output is correct
8 Correct 11 ms 1408 KB Output is correct
9 Correct 11 ms 1280 KB Output is correct
10 Correct 146 ms 68312 KB Output is correct
11 Correct 127 ms 83180 KB Output is correct
12 Correct 20 ms 8828 KB Output is correct