Untitled
unknown
plain_text
a year ago
3.7 kB
6
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