Submission #29787

#	Time	Username	Problem	Language	Result	Execution time	Memory
29787		TAMREF	Palinilap (COI16_palinilap)	C++11	17 / 100	1000 ms	2072 KiB

palinilap

#include <bits/stdc++.h>
using namespace std;
const int mx=5005;
char a[mx],S[mx<<1];
int dp[mx<<1], Z, r,p,np;
void input(){
    scanf("%s",a);
    int N=strlen(a);
    int i=0;
    for(int k=0;k<N;k++){
        S[++i]=a[k];
        S[++i]='*';
    }
    Z=2*N-1;
}
int Manacher(int t, char c){
    r=p=np=0; //p=np
    char x=S[t];
    S[t]=c;
    for(int i=1;i<=Z;i++){
        dp[i]=(i>r)?0:min(dp[2*p-i],r-i);
        for(;i+dp[i]+1<=Z && S[i+dp[i]+1]==S[i-dp[i]-1];++dp[i]);
        if(i+dp[i]>r) p=i,r=i+dp[i];
        if(dp[i]==i-1||dp[i]+i==Z) np+=(S[i]=='*'?(dp[i]+1)>>1:(dp[i]+2)>>1);
        else np+=(S[i]=='*'?(dp[i]>>1):(dp[i]+1)>>1);
    }
    S[t]=x;
    return np;
}
int main(){
    input();
    int X=0;
    for(int i=1;i<=Z;i+=2){
        for(char x='a';x<='z';x++){
            X=max(X,Manacher(i,x));
        }
    }
    printf("%d\n",X);
}

Compilation message (stderr)

palinilap.cpp: In function 'void input()':
palinilap.cpp:7:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",a);
                  ^

• Subtask 1: 17 / 17
• Subtask 2: 0 / 37
• Subtask 3: 0 / 46