比赛 不准粘代码,必须自己写(HS除外) 评测结果 AAAAAAAAAA
题目名称 棋盘制作 最终得分 100
用户昵称 梦那边的美好ET 运行时间 1.831 s
代码语言 C++ 内存使用 106.13 MiB
提交时间 2019-09-24 12:47:11
显示代码纯文本
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cmath>
  5. #include<algorithm>
  6. using namespace std;
  7. int p[2010][2010][2],n,m,bk[2010][2010],f[2010][2010][3],ma1=1,ma2=1;
  8. int main(){
  9. freopen("makechess.in","r",stdin);
  10. freopen("makechess.out","w",stdout);
  11. scanf("%d%d",&n,&m);
  12. for(int i=1;i<=n;i++)
  13. for(int j=1;j<=m;j++)
  14. scanf("%d",&bk[i][j]);
  15. for(int i=1;i<=n;i++){
  16. p[i][1][0]=1;
  17. for(int j=2;j<=m;j++){
  18. if(bk[i][j]!=bk[i][j-1])p[i][j][0]=p[i][j-1][0];
  19. else p[i][j][0]=j;
  20. }
  21. }
  22. for(int i=1;i<=n;i++){
  23. p[i][m][1]=m;
  24. for(int j=m-1;j>=1;j--){
  25. if(bk[i][j]!=bk[i][j+1])p[i][j][1]=p[i][j+1][1];
  26. else p[i][j][1]=j;
  27. }
  28. }
  29. for(int i=1;i<=m;i++){
  30. f[1][i][0]=1;f[1][i][1]=p[1][i][0];f[1][i][2]=p[1][i][1];
  31. ma1=max(ma1,(f[1][i][2]-f[1][i][1]+1));
  32. }
  33. for(int i=2;i<=n;i++){
  34. for(int j=1;j<=m;j++){
  35. if(bk[i][j]!=bk[i-1][j]){
  36. f[i][j][0]=f[i-1][j][0];
  37. f[i][j][1]=max(p[i][j][0],f[i-1][j][1]);
  38. f[i][j][2]=min(p[i][j][1],f[i-1][j][2]);
  39. }
  40. else{
  41. f[i][j][0]=i;
  42. f[i][j][1]=p[i][j][0];
  43. f[i][j][2]=p[i][j][1];
  44. }
  45. ma1=max(ma1,(i-f[i][j][0]+1)*(f[i][j][2]-f[i][j][1]+1));
  46. ma2=max(ma2,min(i-f[i][j][0]+1,f[i][j][2]-f[i][j][1]+1));
  47. }
  48. }
  49. printf("%d\n",ma2*ma2);printf("%d",ma1);
  50. return 0;
  51. }