Untitled

 avatar
unknown
plain_text
10 months ago
1.4 kB
1
Indexable
import java.util.*;
import java.lang.*;

class Main
{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int testcase = sc.nextInt();
		for (int tc = 1; tc <= testcase; tc++) {
			int shape = sc.nextInt();
			int sub_shape = sc.nextInt();
			int k = sc.nextInt();
			int[][] arr = new int[shape][shape];
			int[][] preSum = new int[shape+1][shape+1];
			
			for (int i = 0; i < shape; i++) {
				for (int j = 0; j < shape; j++) {
					arr[i][j] = sc.nextInt();
					preSum[i + 1][j+1] = preSum[i][j+1] + arr[i][j];
				}
			}
			
			for (int i = 1; i < shape+1; i++) {
				for (int j = 0; j < shape - 1; j++) {
					preSum[i][j + 2] += preSum[i][j+1];
				}
			}
			
			
			int[] output = {0,0};
			int distance = preSum[sub_shape][sub_shape] - k;
			long sum_square = distance * distance;
			for (int s = sub_shape; s < shape + 1; s++) {
				for (int t = sub_shape; t < shape+1; t++) {
					int sum = preSum[s][t] - preSum[s][t-sub_shape] - preSum[s - sub_shape][t] + preSum[s - sub_shape][t-sub_shape];
					int tmp = sum - k;
					if ((tmp*tmp) < sum_square) {
						sum_square = tmp*tmp;
						output[0] = s-sub_shape;
						output[1] = t - sub_shape;
						distance = tmp;
					}else if ((tmp*tmp) == sum_square && tmp < distance) {
						output[0] = s - sub_shape;
						output[1] = t - sub_shape;
					}
					
				}
			}
			System.out.println("#" + tc + " " + output[0] + " " + output[1]);
		}
	
	}
}
Editor is loading...
Leave a Comment