Submission #38188430

---

Source Code Expand

#line 2 "/home/zawatin/compro/library/src/template/binary-search.hpp"

#include <cmath>

namespace zawa {

template <class T, class F>
T binary_search(T ok, T ng, const F& f) {
	while (std::abs(ok - ng) > 1) {
		T mid = ((ok + ng) >> 1);
		if (f(mid)) {
			ok = mid;
		}
		else {
			ng = mid;
		}
	}
	return ok;
}

}
#line 2 "/home/zawatin/compro/library/src/dataStructure/accum2d.hpp"

#include <vector>
#include <utility>

namespace zawa {

template <class T>
struct accum2d : std::vector<std::vector<T>> {
	accum2d() {
		(*this).push_back({ T() });
	}
	accum2d(const std::vector<std::vector<T>>& A) : std::vector<std::vector<T>>(A.size() + 1, std::vector<T>(A[0].size() + 1, T())) {
		for (std::size_t i = 0 ; i < A.size() ; i++) {
			for (std::size_t j = 0 ; j < A[i].size() ; j++) {
				(*this)[i + 1][j + 1] = (*this)[i][j + 1] + (*this)[i + 1][j] - (*this)[i][j] + A[i][j];
			}
		}
	}
	T sum(std::size_t y1, std::size_t x1, std::size_t y2, std::size_t x2) {
		return (*this)[y2][x2] - (*this)[y1][x2] - (*this)[y2][x1] + (*this)[y1][x1];
	}
	T sum(std::pair<std::size_t, std::size_t> p1, std::pair<std::size_t, std::size_t> p2) {
		return sum(p1.first, p1.second, p2.first, p2.second);
	}
};

} // namespace zawa
#line 3 "ABC203.test.cpp"

#include <iostream>
#line 6 "ABC203.test.cpp"

int main() {
	int N, K; std::cin >> N >> K;
	std::vector A(N, std::vector(N, 0));
	for (auto& a : A) {
		for (auto& x : a) {
			std::cin >> x;
		}
	}
	auto f = [&](int p) -> bool {
		std::vector B(N, std::vector(N, 0));
		for (int i = 0 ; i < N ; i++) {
			for (int j = 0 ; j < N ; j++) {
				B[i][j] = (A[i][j] <= p);
			}
		}
		zawa::accum2d S(B);
		bool res = false;
		for (int i = 0 ; i + K <= N ; i++) {
			for (int j = 0 ; j + K <= N ; j++) {
				res |= S.sum(i, j, i + K, j + K) >= (K * K + 1) / 2;
			}
		}
		return res;
	};
	std::cout << zawa::binary_search((int)1e9, -1, f) << std::endl;
}

Submission Info

Judge Result