90分求助

P1736 创意吃鱼法

zxTLE @ 2018-03-02 14:30:43

WA第五个点,求dalao帮忙看看```cpp

include<bits/stdc++.h>

using namespace std;

int a[2501][2501],f1[2501][2501],f2[2501][2501],s[2501][2501];

int main() {

 int n,m,ans,sx,sy,k,ex,ey;

 while (scanf("%d%d",&n,&m)!=EOF){
    ans=0;
 memset(a,0,sizeof(a));
 memset(f1,0,sizeof(f1));
 memset(f2,0,sizeof(f2));
 memset(s,0,sizeof(s));
 for (int i=1;i<=n;i++)
  for (int j=1;j<=m;j++)
  {scanf("%d",&a[i][j]);s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];if (a[i][j]==1) {f1[i][j]=f2[i][j]=1;ans=1;s[i][j]++;} }
 for (int i=2;i<=n;i++)
  for (int j=2;j<=m;j++)
  {   if (a[i-1][j-1]==0) continue;
      sx=i-f1[i-1][j-1];
      sy=j-f1[i-1][j-1];
      if (s[i][j]-s[i][sy-1]-s[sx-1][j]+s[sx-1][sy-1]==f1[i-1][j-1]+1) {
   f1[i][j]=f1[i-1][j-1]+1;if (f1[i][j]>ans) ans=f1[i][j];}
  }
 for (int i=2;i<=n;i++)
  for (int j=n-1;j>=1;j--)
  { if (a[i-1][j+1]==0) continue;
      k=f2[i-1][j+1];
      sx=i-k;
      sy=j;
      ex=i;
      ey=j+k;
      if (s[ex][ey]-s[ex][sy-1]-s[sx-1][ey]+s[sx-1][sy-1]==f2[i-1][j+1]+1) 
    { f2[i][j]=f2[i-1][j+1]+1;
      if(f2[i][j]>ans) ans=f2[i][j];
    }
  }
  printf("%d",ans);}

}


by chill @ 2018-03-02 18:28:35


by chill @ 2018-03-02 21:47:55

TLE最后一个点==


by HuangBo @ 2018-03-06 21:18:41

第五个点答案为167 数据诡异之处...


|