Untitled
unknown
plain_text
2 years ago
3.7 kB
8
Indexable
import java.util.*;
import java.io.*;
public class Main {
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try {
str = br.readLine().trim();
} catch (Exception e) {
e.printStackTrace();
}
return str;
}
}
static class FastWriter {
private final BufferedWriter bw;
public FastWriter() {
this.bw = new BufferedWriter(new OutputStreamWriter(System.out));
}
public void print(Object object) throws IOException {
bw.append("" + object);
}
public void println(Object object) throws IOException {
print(object);
bw.append("\n");
}
public void close() throws IOException {
bw.close();
}
}
public static int solve(int[][] matrix) {
int maxArea = 0;
int[] heights = new int[matrix[0].length];
for (int[] row : matrix) {
for (int j = 0; j < row.length; j++) {
heights[j] = (row[j] == 0) ? 0 : heights[j] + 1;
}
maxArea = Math.max(maxArea, largestRectangle(heights));
}
return maxArea;
}
public static int largestRectangle(int[] heights) {
Stack<Integer> stack = new Stack<>();
int maxArea = 0;
int index = 0;
while (index < heights.length) {
if (stack.isEmpty() || heights[index] >= heights[stack.peek()]) {
stack.push(index++);
} else {
int top = stack.pop();
int width = stack.isEmpty() ? index : index - stack.peek() - 1;
maxArea = Math.max(maxArea, heights[top] * width);
}
}
while (!stack.isEmpty()) {
int top = stack.pop();
int width = stack.isEmpty() ? heights.length : heights.length - stack.peek() - 1;
maxArea = Math.max(maxArea, heights[top] * width);
}
return maxArea;
}
public static void main(String[] args) {
try {
FastReader sc = new FastReader();
FastWriter out = new FastWriter();
int T = sc.nextInt();
for (int i = 0; i < T; i++) {
int m = sc.nextInt();
int n = sc.nextInt();
int[][] matrix = new int[m][n];
for (int j = 0; j < m; j++) {
for (int k = 0; k < n; k++) {
matrix[j][k] = sc.nextInt();
}
}
out.println(solve(matrix));
}
out.close();
}
catch (Exception e) {
e.printStackTrace();
return;
}
}
}
Editor is loading...
Leave a Comment