fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static void main (String[] args) throws java.lang.Exception
  11. 	{
  12. 		// your code goes here
  13. 		BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
  14.         String[]size=(in.readLine().trim()).split("\\s+");
  15.         int rows=Integer.parseInt(size[0]);
  16.         int colums=Integer.parseInt(size[1]);
  17.         int[][]matrix=new int[rows][colums];
  18.         for (int i = 0; i <rows ; i++) {
  19.             String[]elements=(in.readLine().trim()).split("\\s+");
  20.             for (int j = 0; j <colums ; j++) {
  21.                 matrix[i][j]=Integer.parseInt(elements[j]);
  22.             }
  23.         }
  24.         int[][]precomput=precomputation(matrix);
  25.         int min=1;
  26.         int max=Math.min(rows,colums);
  27.         int t=Integer.parseInt(in.readLine().trim());
  28.         while (t!=0){
  29.             int threshold=Integer.parseInt(in.readLine().trim());
  30.             System.out.println(sizeofsquare(precomput,min,max,threshold));
  31.             t--;
  32.         }
  33. 	}
  34. 	static int sizeofsquare(int[][]precomput,int min,int max,int threshold){
  35.         while (min<=max){
  36.            int mid=min+(max-min)/2;
  37.            if (ifpossible(mid,precomput,threshold)) {
  38.                if (!ifpossible(mid+1,precomput,threshold)){
  39.                    return mid;
  40.                }else min=mid+1;
  41.            }else {
  42.                max=mid-1;
  43.            }
  44.         }
  45.         return 0;
  46.     }
  47.     static boolean ifpossible(int size,int[][]precomput,int threshold){
  48.  
  49.         for (int i = 0; i <precomput.length-size ; i++) {
  50.             for (int j = 0; j <precomput[i].length-size ; j++) {
  51.                 if (sum(precomput,i,j,i+size-1,j+size-1)<=threshold){
  52.                     return true;
  53.                 }
  54.             }
  55.         }
  56.         return false;
  57.     }
  58.     static long sum(int[][]precomput,int i1,int j1,int i2,int j2){
  59.         long ans=precomput[i2][j2];
  60.         if (j1-1>=0) {
  61.             ans -= precomput[i2][j1 - 1];
  62.             if (i1-1>=0){
  63.                 ans-=precomput[i1-1][j2];
  64.                 ans+=precomput[i1-1][j1-1];
  65.             }
  66.  
  67.         }else {
  68.             if (i1-1>=0){
  69.                 ans-=precomput[i1-1][j2];
  70.             }
  71.  
  72.         }
  73.    return ans;
  74.     }
  75.     static int[][]precomputation(int[][]arr){
  76.         int n=arr.length;
  77.         int m=arr[0].length;;
  78.         int [][]ans=new int[n][m];
  79.         //rowwise
  80.         for (int i = 0; i <n ; i++) {
  81.             ans[i][0]=arr[i][0];
  82.             for (int j = 1; j <m ; j++) {
  83.                 ans[i][j]=ans[i][j-1]+arr[i][j];
  84.             }
  85.         }
  86.         //columnwise
  87.         for (int j = 0; j <m ; j++) {
  88.             for (int i = 1; i <n ; i++) {
  89.                 ans[i][j]+=ans[i-1][j];
  90.             }
  91.         }
  92.         return ans;
  93.  
  94.     }
  95. }
Success #stdin #stdout 0.1s 48428KB
comments (?)
stdin
copy 
3 7
1 1 3 2 4 3 2
1 1 3 2 4 3 2
1 1 3 2 4 3 2
1
4
stdout
copy 
2
https://ideone.com/JmuMGq
language:
Java (HotSpot 12)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!