===== Dragon Tree Fields ===== Komentář k řešení: {{ :courses:a4b33alg:komentare:uloha1komentar.pdf | pdf}}. **Kód řešení v Jave:**

import java.io.*;
import java.util.*;

// ---------------------------------------------------------------------------
//       O N E    F I E L D   R E P R E S E N T A T I O N   
// ---------------------------------------------------------------------------

class Field implements Comparable  {
   int i, j, k;       // coords and size
   long quality;      // sum of field's elements
  
 // constructor  
  public Field ( int i_coord, int j_coord, int k_size , long aSum ){
    i = i_coord; j = j_coord; k = k_size; quality = aSum;  
  }
  
  // check if two fields overlap
  public boolean isDisjointWith( Field f2 ){
    return      
          this.i + this.k <= f2.i  ||  f2.i + f2.k <= this.i
       || this.j + this.k <= f2.j  ||  f2.j + f2.k <= this.j;
  }
  
  @Override
  public int compareTo( Field f2 ){
    if( this.quality < f2.quality ) return -1; else return 1; 
  }
  
  public void print(){ // useful in debugging
    System.out.printf( "[%d] %d %d %d   ", this.quality, this.i-1, this.j-1, this.k );
  }
}

// ---------------------------------------------------------------------------
//                     S O L U T I O N   C L A S S
// ---------------------------------------------------------------------------

public class Solution01 {

static int N;      
static long Q1, Q2;  
static long [][] upLeftSums;   // just one array suffices to solve the problem

// feasible field == field which quality is in the range[Q1, Q2]  
static ArrayList feasibleFields = new ArrayList<>();


static void collectFeasibleFields() {
  long fieldQuality;
  for( int i = 1; i < N; i++ )
    for( int j = 1; j < N; j++ ){
      upLeftSums[i][j] += upLeftSums[i][j-1] + upLeftSums[i-1][j] 
                                             - upLeftSums[i-1][j-1];
      for( int k = 1; k <= Math.min(i, j); k++ ){
        fieldQuality =   upLeftSums[i][j]   - upLeftSums[i-k][j] 
                       - upLeftSums[i][j-k] + upLeftSums[i-k][j-k];
        if( Q1 <= fieldQuality && fieldQuality <= Q2 ) 
          feasibleFields.add( new Field(i, j, k, fieldQuality) );
      }
    }
}

static void findMinimumDifference(){
  int j, imin = -1, jmin=-1; 
  long diff, mindiff = Long.MAX_VALUE;
  
  // go searching, suppose feasible fields are sorted by their qualities
  for( int i = 0; i < feasibleFields.size()-1; i++ ){
    j = i;
    while( true ) {
      j++;
      if( j >=  feasibleFields.size() ) break;
      if( feasibleFields.get(i).isDisjointWith( feasibleFields.get(j) ) ){
        diff = feasibleFields.get(j).quality - feasibleFields.get(i).quality;
        if( diff <= mindiff ) // register new min
          { mindiff = diff; imin = i; jmin = j; }
        break;
      }
    } // while 
  } // for
  System.out.printf( "%d %d\n", feasibleFields.get(imin).quality, 
                                feasibleFields.get(jmin).quality );  
}

// ..........................................................................
//                   M A I N 
public static void main(String[] args)  throws IOException {
  loadData();
  collectFeasibleFields();
  Collections.sort( feasibleFields );
  findMinimumDifference();
}
  
// ..........................................................................
//                 I N P U T 
static void loadData()  throws IOException {
  BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
  StringTokenizer st = new StringTokenizer( br.readLine() );
  
  N = Integer.valueOf( st.nextToken() );
  
  // artificially, the array is bigger, it has additional zero row and column
  // at the top and at the left ([i][0] and [0][j] are all  0), 
  // this trick simplifies processing  -- no need for border checking.
  upLeftSums = new long [N+1][N+1]; 
  
  for( int i = 1; i <= N; i++ ){
    st = new StringTokenizer( br.readLine() );
    for( int j = 1; j <= N; j++ )
      upLeftSums [i][j] = Long.valueOf( st.nextToken() );
  }
  
  st = new StringTokenizer( br.readLine() );
  Q1 = Long.valueOf( st.nextToken() );
  Q2 = Long.valueOf( st.nextToken() );
} 

}