#include "quality.h"
#include <vector>
void merge(int start, int end, int* arr, int* tmp) {
int i, j, k, mid = (start + end) / 2;
if(mid <= start) return;
merge(start, mid, arr, tmp);
merge(mid, end, arr, tmp);
for(i = start, j = mid, k = start; i < mid && j < end; k++) {
if(arr[i] < arr[j]) {
tmp[k] = arr[i];
i++;
}
else {
tmp[k] = arr[j];
j++;
}
}
for( ; i < mid; i++) {
tmp[k] = arr[i];
k++;
}
for( ; j < end; j++) {
tmp[k] = arr[j];
k++;
}
for(i = start; i < end; i++) {
arr[i] = tmp[i];
}
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int i, j, k, l, t = (H*W)/2, m = 2000000024;
//int *tmp, *arr;
//tmp = (int *)malloc(9000001 * sizeof(int));
//arr = (int *)malloc(9000001 * sizeof(int));
int tmp[9000012], arr[9000012], len = 0, c;
vector <int> rice;
/*/*
for(k = 0; k < H; k++) {
for(l = 0; l < W; j++) {
arr[len] = Q[i][j];
len++;
}
}
merge(0, len, arr, tmp);
if(m > arr[t]) m = arr[t];
/**/
for(i = 0; i <= R-H; i++) {
for(j = 0; j <= C-W; j++) {
for(k = i; k < H+i; k++) {
for(l = j; l < W+j; l++) {
arr[len] = Q[k][l];
len++;
}
}
merge(0, len, arr, tmp);
/*/*
for(int p = 0; p < len; p++) {
printf("%d ", arr[p]);
}
printf("\n");
/**/
if(m > arr[t]) m = arr[t];
len = 0;
}
}
return m;
}
