Editorial for Hình chữ nhật 0 1


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const fi='';
      fo='';
      maxn=1010;
var m,n,re:longint;
    a:array[0..maxn,0..maxn] of longint;
    st,pos:array[0..2*maxn] of longint;

procedure rf;
var i,j,t:longint;
begin
     assign(input,fi);
     reset(input);
     readln(m,n);
     re:=0;
     fillchar(a,sizeof(a),0);
     for i:=1 to m do
     begin
          for j:=1 to n do
          begin
               read(t);
               if t=0 then a[i,j]:=0
               else
               begin
                    a[i,j]:=a[i-1,j]+1;
                    if a[i,j]>re then re:=a[i,j];
               end;
          end;
          readln;
     end;
     close(input);
end;

procedure pr;
var i,j,now,k,q,s:longint;
begin
     if re=0 then exit;
     st[0]:=0; pos[0]:=0;
     for i:=1 to m do
     begin
          j:=1; now:=0;
          repeat
                if a[i,j]>0 then
                begin
                     if a[i,j]>=st[now] then
                     begin
                          inc(now);
                          st[now]:=a[i,j]; pos[now]:=j;
                     end
                     else
                     begin
                          k:=now;
                          while (st[now]>a[i,j]) and (now>0) do dec(now);
                          inc(now);
                          for q:=k-1 downto now do
                          begin
                               s:=st[q]*(pos[k]-pos[q]+1);
                               if s>re then re:=s;
                          end;
                          st[now]:=a[i,j];
                          inc(now);
                          st[now]:=a[i,j]; pos[now]:=j;
                     end;
                end
                else
                begin
                     if a[i,j-1]>0 then
                     begin
                          for q:=now downto 1 do
                          begin
                               s:=st[q]*(j-pos[q]);
                               if s>re then re:=s;
                          end;
                          now:=0;
                     end;
                end;
                inc(j);
          until j>n+1;
     end;
end;

procedure wf;
begin
     assign(output,fo);
     rewrite(output);
     write(re);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include<cstdio>

const int N = 1005;

/* Stack */
int stack[N], topS;
void init() { topS = 0; }
int top() { return stack[topS-1]; }
int pop() { return stack[--topS]; }
void push(const int &x) { stack[topS++] = x; }
/* End of Stack */

int m, n, a[N][N], f[N][N], left[N], right[N];
/* f[y][x] = k <=> a[y..y+k-1][x] = 11..., k max */

void enter() {
    scanf("%d%d",&m,&n);
    for(int i = 0; i < m; ++i)
        for(int j = 0; j < n; ++j)
            scanf("%d", &a[i][j]);
}

void calcF() {
    for(int j = 0; j < n; ++j)
        for(int i = m-1; i >= 0; --i)
            f[i][j] = a[i][j] ? f[i+1][j] + 1 : 0;
}

void maximize(int &a, const int &b) { if(a < b) a = b; }

void solve() {
    int res = 0;
    for(int i = 0; i < m; ++i) {
        left[0] = 0; init();
        for(int j = 1; j < n; ++j)
            if(f[i][j] > f[i][j-1]) left[j] = j, push(j-1);
            else {
                while(topS && f[i][j] <= f[i][top()]) pop();
                left[j] = topS ? top() + 1 : 0;
            }
        right[n-1] = n-1; init();
        for(int j = n-2; j >= 0; --j)
            if(f[i][j] > f[i][j+1]) right[j] = j, push(j+1);
            else {
                while(topS && f[i][j] <= f[i][top()]) pop();
                right[j] = topS ? top() - 1 : n-1;
            }
        for(int j = 0; j < n; ++j) maximize(res, (right[j] - left[j] + 1) * f[i][j]);
    }
    printf("%d\n", res);
}

int main() {
    enter();
    calcF();
    solve();
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int a[N][N];
int h[N];

int c[N][N];

int n, m;

struct Rectangle {
    int h, w;
} s[N];
int size;

int main() {
    ios::sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) cin >> a[i][j];
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) h[j] = a[i][j] ? h[j] + 1 : 0;
        for (int j = 0; j <= n + 1; ++j) {
            int w = 0;
            while (size > 0 && s[size].h >= h[j]) {
                int cur_h = max(s[size - 1].h, h[j]);
                w += s[size].w;
                ++c[cur_h + 1][w];
                --c[s[size].h + 1][w];
                --size;
            }
            ++size;
            s[size].w = w + 1;
            s[size].h = h[j];
        }
    }
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) c[i + 1][j] += c[i][j];
        int c1 = 0, c2 = 0;
        for (int j = n; j >= 1; --j) {
            c1 += c[i][j];
            c2 += c1;
            c[i][j] = c2;
        }
    }
    int ans = 0;
    for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) if (c[i][j])
        ans = max(ans, i * j);
    cout << ans << endl;
    return 0;
}

Code mẫu của RR

uses math;
var
  res,top,i,j,m,n:longint;
  a:array[1..1011,1..1011] of longint;
  down,left,right,stack:array[0..1011] of longint;
begin
  read(m,n);
  for i:=1 to m do
  for j:=1 to n do
    read(a[i,j]);

  for i:=1 to m do
    begin
      for j:=1 to n do
        if a[i,j]=1 then down[j]:=down[j]+1
        else down[j]:=0;

      top:=0; stack[0]:=0;
      for j:=1 to n do
        begin
          while (top>0) and (down[stack[top]]>=down[j]) do dec(top);
          left[j]:=stack[top]+1;
          inc(top); stack[top]:=j;
        end;
      top:=0; stack[0]:=n+1;
      for j:=n downto 1 do
        begin
          while (top>0) and (down[stack[top]]>=down[j]) do dec(top);
          right[j]:=stack[top]-1;
          inc(top); stack[top]:=j;
        end;

      for j:=1 to n do
        res:=max(res,down[j]*(right[j]-left[j]+1));
    end;

  writeln(res);
end.

Code mẫu của hieult

#include<string>
#include<vector>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
//#include<conio.h>

using namespace std;

#define FOR(i, a, b) for(int i=(a), _b=(b); i < _b; ++i)
#define FORU(i, a, b) for(int i=(a), _b=(b); i <= _b; ++i)
#define FORD(i, a, b) for(int i=(a), _b=(b); i >= _b; --i)
#define maxn 1111

int l[2][maxn], r[2][maxn], h[2][maxn], a[maxn][maxn];

int main(){
    //freopen("QBRECT.in","r",stdin);
     int m,n,kq = 0;
     scanf("%d %d",&m,&n);
     FORU(i, 1, m) FORU(j, 1, n) scanf("%d",&a[i][j]);
     memset(h,0,sizeof(h));
     FORU(i, 1, m) FOR(t, 1, 2){
          FORU(j, 1, n) {
               if(a[i][j]==t)
                     h[t][j]++;
               else h[t][j] = 0;
          }
          h[t][0] = -1; h[t][n+1] = -1;
          FORU(j, 1, n){
               l[t][j] = j;
               while(h[t][l[t][j]-1]>=h[t][j]) l[t][j] = l[t][l[t][j]-1];
          }
          FORD(j, n, 1){
               r[t][j] = j;
               while(h[t][r[t][j]+1]>=h[t][j]) r[t][j] = r[t][r[t][j]+1];
          }
          FORU(j, 1, n){
               kq = max(kq,h[t][j]*(r[t][j]-l[t][j]+1));
          }
     }
     printf("%d",kq);
     //getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
program QBRECT;
const
  input  = '';
  output = '';
  maxn = 1000;
var
  s: array[1..maxn,1..maxn] of integer;
  stack,a,left,right: array[0..maxn] of integer;
  top,n,m,res: integer;

procedure init;
var
  f: text;
  i,j: integer;
begin
  assign(f, input);
    reset(f);

  readln(f, m, n);
  for i := 1 to m do
    for j := 1 to n do read(f, s[i,j]);

  close(f);
end;

procedure push(v: integer);
begin
  inc(top);
  stack[top] := v;
end;

procedure calc;
var
  i: integer;
begin
  top := 0;
  for i := 1 to n do
    begin
      while (top > 0) and (a[stack[top]] >= a[i]) do dec(top);
      if top = 0 then left[i] := 1 else left[i] := stack[top] + 1;
      push(i);
    end;

  top := 0;
  for i := n downto 1 do
    begin
      while (top > 0) and (a[stack[top]] >= a[i]) do dec(top);
      if top = 0 then right[i] := n else right[i] := stack[top] - 1;
      push(i);
    end;

  for i := 1 to n do
    if res < (right[i] - left[i] + 1) * a[i] then res := (right[i] - left[i] + 1) * a[i];
end;

procedure solve;
var
  i,j: integer;
begin
  res := 0;
  fillchar(a, sizeof(a), 0);

  for i := 1 to m do
    begin
      for j := 1 to n do
        if s[i,j] = 1 then inc(a[j]) else a[j] := 0;
      calc;
    end;
end;

procedure printresult;
var
  f: text;
begin
  assign(f, output);
    rewrite(f);
    writeln(f, res);
  close(f);
end;

begin
  init;
  solve;
  printresult;
end.

Code mẫu của skyvn97

#include<stdio.h>
#define MAX   1111
int a[MAX][MAX];
int h[MAX][MAX];
int stack[MAX];
int l[MAX];
int r[MAX];
int max,m,n;
int size;
void init(void)
{
     scanf("%d",&m);
     scanf("%d",&n);
     int i,j;
     for (i=1;i<=n;i=i+1) h[0][i]=0;
     for (i=1;i<=m;i=i+1)
         for (j=1;j<=n;j=j+1)
             {
              scanf("%d",&a[i][j]);
              if (a[i][j]==0) h[i][j]=0;
              else h[i][j]=h[i-1][j]+1;              
             }     
     max=0;   
}
void process(void)
{
     int i,j,tmp;
     for (i=1;i<=m;i=i+1)
         {
          size=0;
          l[1]=1;
          for (j=2;j<=n;j=j+1)
              {
               if (h[i][j]>h[i][j-1])
                  {
                   l[j]=j;
                   size++;
                   stack[size]=j-1;
                  }
               else
                   {
                    while ((size>0) && (h[i][stack[size]]>=h[i][j])) size--;
                    if (size==0) l[j]=1;
                    else l[j]=stack[size]+1;
                   }
              }
          size=0;
          r[n]=n;
          for (j=n-1;j>=1;j=j-1)
              {
               if (h[i][j]>h[i][j+1])
                  {
                   r[j]=j;
                   size++;
                   stack[size]=j+1;
                  }
               else
                   {
                    while ((size>0) && (h[i][stack[size]]>=h[i][j])) size--;
                    if (size==0) r[j]=n;
                    else r[j]=stack[size]-1;
                   }
              }
          tmp=0;
          for (j=1;j<=n;j=j+1)
              if (tmp<h[i][j]*(r[j]-l[j]+1)) tmp=h[i][j]*(r[j]-l[j]+1);   
          if (max<tmp) max=tmp;
         }
     printf("%d",max);
}
int main(void)
{
    init();
    process(); 
}

Code mẫu của khuc_tuan

#include <stdio.h>

int m, n;
int h[1000], l[1000], r[1000];

int main() {
    int i, j, xx, t, result = 0;
    scanf("%d%d", &m, &n);
    for(i=0;i<m;++i) {
        for(j=0;j<n;++j) {
            scanf("%d", &xx);
            h[j] = (xx==1) ? h[j]+1 : 0;
        }
        for(j=0;j<n;++j) {
            t = j-1;
            while(t>=0 && h[t]>=h[j]) t = l[t];
            l[j] = t;
        }
        for(j=n-1;j>=0;--j) {
            t = j+1;
            while(t<n && h[t]>=h[j]) t = r[t];
            r[j] = t;
            result >?= h[j] * (r[j]-l[j]-1);
        }
    }
    printf("%d\n", result);
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.