C++11(clang++ 3.9) 解法, 执行用时: 334ms, 内存消耗: 35952K, 提交时间: 2020-06-01 10:11:58

#include<stdio.h>
#include<algorithm>
#define N 2222
using namespace std;
int n,m,G[N][N],HR[N][N],LR[N][N],Max,pos,Ans;
void Manacher(int k)
{
    Max=0;pos=0;
    for(int i=1;i<=m;i++)
    {
        if(i>Max)HR[k][i]=1;
        else HR[k][i]=min(Max-i+1,HR[k][2*pos-i]);
        while(i-HR[k][i]>0&&i+HR[k][i]<=m&&G[k][i-HR[k][i]]==G[k][i+HR[k][i]])HR[k][i]++;
        if(i+HR[k][i]-1>Max)Max=i+HR[k][i]-1,pos=i;
    }
}
void manacher(int k)
{
    Max=0;pos=0;
    for(int i=1;i<=n;i++)
    {
        if(i>Max)LR[k][i]=1;
        else LR[k][i]=min(Max-i+1,LR[k][2*pos-i]);
        while(i-LR[k][i]>0&&i+LR[k][i]<=n&&G[i-LR[k][i]][k]==G[i+LR[k][i]][k])LR[k][i]++;
        if(i+LR[k][i]-1>Max)Max=i+LR[k][i]-1,pos=i;
    }
}
int main()
{
    int i,j,k,u,d,l,r,Min;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)scanf("%d",&G[i<<1][j<<1]);
    n=n<<1|1;m=m<<1|1;
    for(i=1;i<=n;i++)if(i-1&1)Manacher(i);
    for(i=1;i<=m;i++)if(i-1&1)manacher(i);
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    if(i+j-1&1)
    {
        u=d=i;l=r=j;k=2;
        u--;d++;l--;r++;
        if(HR[i][j])Min=min(HR[i][j],LR[j][i]);
        else Min=n;
        while((Min>=k&&HR[u][j]>=k&&HR[d][j]>=k&&LR[l][i]>=k&&LR[r][i]>=k)||(k+i-1&1))
        {
            if(HR[u][j])Min=min(HR[u][j],Min);
            if(HR[d][j])Min=min(HR[d][j],Min);
            if(LR[l][i])Min=min(LR[l][i],Min);
            if(LR[r][i])Min=min(LR[r][i],Min);
            u--;d++;l--;r++;k++;
        }
        if(j&1)Ans+=k-2>>1;
        else Ans+=k-1>>1;
    }
    printf("%d",Ans);
}