oj.uz

Submission #5523

# Submission time Handle Problem Language Result Execution time Memory
5523 2014-05-05T12:26:39 Z gs12117 Palindromes (APIO14_palindrome) C++
47 / 100
 1000 ms 48268 KB 
#include<stdio.h>
#include<string.h>
#include<algorithm>
int n;
char a[300100];
int b[600100];
int q[30][300100];
int qe[30];
int grp[600100];
int grd[600100];
int ngrp[600100];
int ngrd[600100];
int grn;
int grk;
int ans;
int main(){
    int i,j,k,pn;
    scanf("%s",a);
    n=strlen(a);
    for(i=0;i<n;i++){
        b[2*i+2]=a[i]-'a'+1;
    }
    b[0]=27;
    b[2*n+2]=28;
    n=2*n+3;
    for(i=0;i<n;i++){
        grd[i]=i;
    }
    grn=n;
    for(i=0;grn;i++){
        for(j=0;j<29;j++){
            qe[j]=0;
        }
        for(j=0;j<grn;j++){
            if(b[grd[j]-i]==b[grd[j]+i]){
                k=b[grd[j]-i];
                q[k][qe[k]]=j;
                qe[k]++;
            }
        }
        grn=0;
        grk=0;
        for(j=0;j<29;j++){
            pn=0;
            for(k=0;k<qe[j];k++){
                ngrp[grn]=grk;
                ngrd[grn]=grd[q[j][k]];
                grn++;
                pn++;
                if(k+1==qe[j]||grp[q[j][k]]!=grp[q[j][k+1]]){
                    if(ans<pn*i)ans=pn*i;
                    pn=0;
                    grk++;
                }
            }
        }
        for(j=0;j<grn;j++){
            grd[j]=ngrd[j];
            grp[j]=ngrp[j];
        }
    }
    printf("%d",ans);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 48268 KB Output is correct - answer is '7'
2 Correct 0 ms 48268 KB Output is correct - answer is '4'
3 Correct 0 ms 48268 KB Output is correct - answer is '9'
4 Correct 0 ms 48268 KB Output is correct - answer is '1'
5 Correct 0 ms 48268 KB Output is correct - answer is '1'
6 Correct 0 ms 48268 KB Output is correct - answer is '2'
7 Correct 0 ms 48268 KB Output is correct - answer is '3'
8 Correct 0 ms 48268 KB Output is correct - answer is '3'
9 Correct 0 ms 48268 KB Output is correct - answer is '15'
10 Correct 0 ms 48268 KB Output is correct - answer is '24'
11 Correct 0 ms 48268 KB Output is correct - answer is '10'
12 Correct 0 ms 48268 KB Output is correct - answer is '24'
13 Correct 0 ms 48268 KB Output is correct - answer is '25'
14 Correct 0 ms 48268 KB Output is correct - answer is '28'
15 Correct 0 ms 48268 KB Output is correct - answer is '2'
16 Correct 0 ms 48268 KB Output is correct - answer is '1'
17 Correct 0 ms 48268 KB Output is correct - answer is '15'
18 Correct 0 ms 48268 KB Output is correct - answer is '18'
19 Correct 0 ms 48268 KB Output is correct - answer is '1176'
20 Correct 0 ms 48268 KB Output is correct - answer is '1225'
21 Correct 0 ms 48268 KB Output is correct - answer is '136'
22 Correct 0 ms 48268 KB Output is correct - answer is '45'
23 Correct 0 ms 48268 KB Output is correct - answer is '2500'
24 Correct 0 ms 48268 KB Output is correct - answer is '380'
25 Correct 0 ms 48268 KB Output is correct - answer is '2304'
26 Correct 0 ms 48268 KB Output is correct - answer is '110'
27 Correct 0 ms 48268 KB Output is correct - answer is '93'
28 Correct 0 ms 48268 KB Output is correct - answer is '729'
29 Correct 0 ms 48268 KB Output is correct - answer is '132'
30 Correct 0 ms 48268 KB Output is correct - answer is '7'
31 Correct 0 ms 48268 KB Output is correct - answer is '8'
32 Correct 0 ms 48268 KB Output is correct - answer is '64'

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 48268 KB Output is correct - answer is '124251'
2 Correct 0 ms 48268 KB Output is correct - answer is '38226'
3 Correct 8 ms 48268 KB Output is correct - answer is '249500'
4 Correct 0 ms 48268 KB Output is correct - answer is '5778'
5 Correct 8 ms 48268 KB Output is correct - answer is '247506'
6 Correct 8 ms 48268 KB Output is correct - answer is '248004'
7 Correct 0 ms 48268 KB Output is correct - answer is '973'
8 Correct 4 ms 48268 KB Output is correct - answer is '123753'
9 Correct 0 ms 48268 KB Output is correct - answer is '2346'
10 Correct 0 ms 48268 KB Output is correct - answer is '53'
11 Correct 0 ms 48268 KB Output is correct - answer is '52'
12 Correct 0 ms 48268 KB Output is correct - answer is '976'

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 48268 KB Output is correct - answer is '12497500'
2 Correct 244 ms 48268 KB Output is correct - answer is '6481800'
3 Correct 852 ms 48268 KB Output is correct - answer is '25000000'
4 Correct 636 ms 48268 KB Output is correct - answer is '17816841'
5 Correct 0 ms 48268 KB Output is correct - answer is '9945'
6 Correct 20 ms 48268 KB Output is correct - answer is '504100'
7 Correct 84 ms 48268 KB Output is correct - answer is '1512930'
8 Correct 0 ms 48268 KB Output is correct - answer is '413'
9 Correct 0 ms 48268 KB Output is correct - answer is '428'
10 Correct 0 ms 48268 KB Output is correct - answer is '7232'

Subtask #4
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 48264 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -