# 11621: 【原1621】未命名

### 题目描述

author: Chika 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1621 ﻿## Description

## Output Format

``````一行，输出最大全白子矩形的大小。
``````

## Sample Input

``````2
11
11
``````

## Sample Output

``````4
``````

## Limits

• 对于40%的数据，n <= 8
• 对于100%的数据，n <= 1000

## q4x3's solution

``````/**
* 用一个矩阵存储每个格子左侧最长的连续白子序列(包括自己)
* 对矩阵的每一列排序后，遍历，更新答案
**/
#include <iostream>

using namespace std;

template <typename T>
void merge(int lo, int mi, int hi, T* a)
{
T* A = a + lo;
int lb = mi - lo;
T* B = new T[lb];
T* BB = B;
for(int i = 0;i < lb;++ i)
B[i] = A[i];
int lc = hi - mi;
T* C = a + mi;
int cnt = 0;
while(1) {
if ((lb == 0) && (lc == 0)) break;
if (lb == 0) {
A[cnt] = C[0];
++ cnt; ++ C; -- lc;
}
else if (lc == 0) {
A[cnt] = B[0];
++ cnt; ++ B; --lb;
}
else {
if(B[0] < C[0]) {
A[cnt] = B[0];
++ cnt; ++ B; -- lb;
}
else {
A[cnt] = C[0];
++ cnt; ++ C; -- lc;
}
}
}
delete []BB;
}

template <typename T>
void mergeSort(int lo, int hi, T* A)
{
if(hi - lo < 2) return;
int mi = (lo + hi) / 2;
mergeSort(lo, mi, A); mergeSort(mi, hi, A);
merge(lo, mi, hi, A);
}

int n, b[1010][1010], c[1010], ans;
char a[1010][1010];

int main() {
cin >> n;
for(int i = 0;i < n;++ i)
cin >> a[i];
for(int i = 0;i < n;++ i)
for(int j = 0;j < n;++ j) {
int tmp = j;
while(a[i][tmp] == '1') {
-- tmp;
++ b[i][j];
}
}
for(int i = 0;i < n;++ i) {
for(int j = 0;j < n;++ j)
c[j] = b[j][i];
mergeSort(0, n, c);
for(int j = 0;j < n;++ j) {
if(c[j] * (n - j) > ans) ans = c[j] * (n - j);
}
}
cout << ans << endl;
}
``````

## victrid's solution

``````#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int* MergeSort(int* list, int listSize) {
if (listSize == 1)
return list;
if (listSize == 2) {
if (list[0] < list[1]) {
int temp = list[0];
list[0]  = list[1];
list[1]  = temp;
return list;
}
return list;
}
int* tmplist = new int[listSize];
int* llst    = MergeSort(list, listSize / 2);
int* rlst    = MergeSort(list + listSize / 2, listSize - listSize / 2);
int lct = 0, rct = 0;
while (lct + rct != listSize) {
if ((llst[lct] >= rlst[rct] && lct < listSize / 2) || rct >= listSize - listSize / 2) {
tmplist[lct + rct] = llst[lct];
lct++;
} else {
tmplist[lct + rct] = rlst[rct];
rct++;
}
}
memcpy(list, tmplist, sizeof(int) * listSize);
delete[] tmplist;
return list;
}
int main() {
int n;
cin >> n;
int** mat = new int*[n];
for (int i = 0; i < n; i++) {
mat[i] = new int[n]();
}
for (int i = 0; i < n; i++) {
int suml = 0;
char proc;
cin.get();
for (int j = 0; j < n; j++) {
scanf("%c", &proc);
proc -= '0';
suml += proc;
suml *= proc;
// suml += proc *= proc; /*fatal*/
mat[j][i] = suml;
}
}
int pzmax = 0;
int proc  = 0;
for (int j = 0; j < n; j++) {
MergeSort(mat[j], n);
for (int i = 0; i < n; i++) {
proc  = mat[j][i] * (i + 1);
pzmax = pzmax > proc ? pzmax : proc;
}
}
cout << pzmax;
return 0;
}
``````

## WashSwang's solution

``````#include <iostream>
using namespace std;
int n,sorted[1001],pre[1001],cur,ans;
char mat[1001][1001];
void qsort(int l,int r){
if (l+1>=r) return;
int i=l,j=r-1,k=sorted[l];
while (i<j){
while (i<j&&sorted[j]<=k) j--;
if (i<j) sorted[i++]=sorted[j];
while (i<j&&sorted[i]>=k) i++;
if (i<j) sorted[j--]=sorted[i];
}
sorted[i]=k;
qsort(l,i);
qsort(i+1,r);
}
int main() {
cin>>n;
for (int i=0;i<n;++i)
cin>>mat[i];
for (int i=0;i<n;++i)
{
for (int j=0;j<n;++j)
if (mat[j][i]!='1')
sorted[j]=pre[j]=0;
else sorted[j]=pre[j]=pre[j]+1;
qsort(0,n);
cur=sorted[0];
for (int j=0;j<n;++j){
cur=min(cur,sorted[j]);
ans=max(ans,cur*(j+1));
}
}
cout<<ans;
return 0;
}
``````

## zqy2018's solution

``````/*
Hint: build triangular matrix
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, len[1005] = {0}, tmp[1005];
char s[1005][1005];
void init(){
for (int i = 0; i < n; ++i)
scanf("%s", s[i]);
}
void solve(){
int ans = 0;
for (int i = n - 1; i >= 0; --i){
for (int j = 0; j < n; ++j)
len[j] = (s[j][i] == '0' ? 0: len[j] + 1),
tmp[j] = len[j];
sort(tmp, tmp + n);
for (int j = n - 1; j >= 0; --j)
ans = max(ans, tmp[j] * (n - j));
}
printf("%d\n", ans);
}
int main(){
init();
solve();
return 0;
}
``````