比赛 EYOI与SBOI开学欢乐赛11th 评测结果 MMMMMMMMMM
题目名称 矩形地块(A Strip of Land) 最终得分 0
用户昵称 guobinbin 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2022-10-14 22:24:55
显示代码纯文本
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int m,n,c,h[750][750];
  4. int ini[750][750]={};
  5. int ans=1;
  6. int t;
  7. int mi[750][750][105];
  8. int ma[750][750][105];
  9. int main(){
  10. freopen("land.in","r",stdin);
  11. freopen("land.out","w",stdout);
  12. scanf("%d%d%d",&m,&n,&c);
  13. for(int i=1;i<=n;i++){
  14. for(int j=1;j<=m;j++){
  15. scanf("%d",&h[i][j]);
  16. }
  17. for(int j=1;j<=m;j++){
  18. for(int k=j;k<=m&&k<=j+99;k++){
  19. if(k==j||(abs(mi[i][j][k-j]-h[i][k])<=c&&abs(ma[i][j][k-j]-h[i][k])<=c)){
  20. ini[i][j]++;
  21. if(k==j){
  22. mi[i][j][1]=ma[i][j][1]=h[i][j];
  23. }else{
  24. mi[i][j][k-j+1]=min(mi[i][j][k-j],h[i][k]);
  25. ma[i][j][k-j+1]=max(ma[i][j][k-j],h[i][k]);
  26. }
  27. }else{
  28. break;
  29. }
  30. }
  31. }
  32. }
  33. for(int i=1;i<=n;i++){
  34. for(int j=1;j<=m;j++){
  35. t=1;
  36. while(ini[i][j]>0){
  37. while(i+t-1<n&&ini[i+t][j]>=ini[i][j]&&ma[i][j][ini[i][j]]-mi[i+t][j][ini[i][j]]<=c&&ma[i+t][j][ini[i][j]]-mi[i][j][ini[i][j]]<=c){
  38. for(int k=1;k<=ini[i][j];k++){
  39. ma[i][j][k]=max(ma[i][j][k],ma[i+t][j][k]);
  40. mi[i][j][k]=min(mi[i][j][k],mi[i+t][j][k]);
  41. }
  42. t++;
  43. }
  44. ans=max(ans,t*ini[i][j]);
  45. ini[i][j]--;
  46. if(i+t-1==n){
  47. ini[i][j]=0;
  48. }
  49. }
  50. }
  51. }
  52. printf("%d",ans);
  53. fclose(stdin);
  54. fclose(stdout);
  55. return 0;
  56. }