oj.uz

Submission #156335

# Submission time Handle Problem Language Result Execution time Memory
156335 2019-10-05T08:21:43 Z nahid08 Palindromes (APIO14_palindrome) C++14
47 / 100
 1000 ms 12436 KB 
/*
Nahid Hossain
Jahangirnagar University
Roll:54
*/
#include<bits/stdc++.h>
#define ll          long long int
#define db          double
#define pf          printf
#define sf          scanf
#define ff          first
#define ss          second
#define clr         clear()
#define sz          size()
#define pb          push_back
#define mk          make_pair
#define pi          acos(-1)
#define inf         1000000000000000000
//#define mod         1000000007
#define ull         unsigned long long int
#define f(i,k,n)    for(ll i=k;i<n;i++)
#define fr(i,n,k)   for(i=n;i>=k;i--)
#define ent(a)      scanf("%lld",&a)
#define ent2(a,b)   scanf("%lld%lld",&a,&b)
#define ent3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define mem(a)      memset(a,0,sizeof(a))
#define vec(v,s)    vector<ll>v[s]
#define arr(a,s)    ll a[s];
//#define check(n,pos) (n&(1<<pos))
//#define set(n,pos)  (n|(1<<pos))
//knight and king//
int dr[]={2, 2, -2, -2, 1, -1, 1, -1};
int dc[]={1,-1,  1, -1, 2,  2,-2, -2};
int dr1[]={0, 0, 0, 1, 1, 1, -1, -1, -1};
int dc1[]={-1,0, 1,-1, 0, 1, -1, 0,   1};
int dr2[]={0, 0, 1, -1};
int dc2[]={1,-1, 0,  0};
////////////////////////////
using namespace std;
#define ma 100004


string s; // 0-indexed
int t, idx, tree[ma][26], link[ma], len[ma], occ[ma], n;
void extend(int p) {
    while(s[p - len[t] - 1] != s[p]) t = link[t];
    int ch = s[p] - 'a', x = link[t];
    while(s[p - len[x] - 1] != s[p]) x = link[x];
    if(!tree[t][ch]) {
        tree[t][ch] = ++idx, len[idx] = len[t] + 2;
        link[idx] = len[idx] == 1 ? 2 : tree[x][ch];
    } t = tree[t][ch], ++occ[t];
}

void build() {
    len[1] = -1, len[2] = 0;
    link[1] = link[2] = 1;
    t = idx = 2;
    n=s.sz;
    for(int i = 0; i < n; i++) extend(i);
    for(int i = idx; i > 2; i--) {
        occ[link[i]] += occ[i];
    }
}


int main()
{
    cin>>s;

    build( );

    ll i,j,ans=0;

    for(i=3;i<=idx;i++)
    {
        ll p=len[i]*occ[i];
        ans=max(ans,p);
    }
    cout<<ans<<endl;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:73:10: warning: unused variable 'j' [-Wunused-variable]
     ll i,j,ans=0;
          ^

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 380 KB Output is correct
4 Correct 2 ms 376 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 380 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 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 380 KB Output is correct
18 Correct 2 ms 404 KB Output is correct
19 Correct 2 ms 380 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 376 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 4 ms 376 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 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 476 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 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 504 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1528 KB Output is correct
2 Correct 4 ms 1528 KB Output is correct
3 Correct 4 ms 1528 KB Output is correct
4 Correct 5 ms 1500 KB Output is correct
5 Correct 4 ms 1528 KB Output is correct
6 Correct 4 ms 1528 KB Output is correct
7 Correct 5 ms 1528 KB Output is correct
8 Correct 3 ms 380 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 1144 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 12028 KB Output is correct
2 Correct 23 ms 12024 KB Output is correct
3 Incorrect 23 ms 11996 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 12436 KB Time limit exceeded
2 Halted 0 ms 0 KB -