Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <set>
- #include <map>
- #include <cstring>
- #include <algorithm>
- #include <stack>
- #include <queue>
- #include <fstream>
- using namespace std;
- typedef int ll;
- set<ll> smaller_values, greater_values;
- int n, k;
- void insert_value(ll & x) {
- ll max_in_smaller_values = *smaller_values.rbegin();
- if(max_in_smaller_values < x) {
- greater_values.insert(x);
- if(greater_values.size() > k / 2) {
- ll min_in_greater = *greater_values.begin();
- smaller_values.insert(min_in_greater);
- greater_values.erase(greater_values.find(min_in_greater));
- }
- }
- else {
- smaller_values.insert(x);
- if(smaller_values.size() > (k + 1) / 2) {
- ll tmp_max_in_smaller = *smaller_values.rbegin();
- greater_values.insert(tmp_max_in_smaller);
- smaller_values.erase(smaller_values.find(tmp_max_in_smaller));
- }
- }
- }
- void remove_element(ll & x) {
- if(greater_values.find(x) != greater_values.end()) {
- greater_values.erase(greater_values.find(x));
- }
- else if(smaller_values.find(x) != smaller_values.end()) {
- smaller_values.erase(smaller_values.find(x));
- }
- if(smaller_values.empty()) {
- ll min_in_greater = *greater_values.begin();
- smaller_values.insert(min_in_greater);
- greater_values.erase(greater_values.find(min_in_greater));
- }
- }
- ll mat[888][888];
- int main(){
- ios_base::sync_with_stdio(false);
- // ifstream cinx("input.txt");
- cin >> n >> k;
- ll ss = 2e9;
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < n; j++) {
- cin >> mat[i][j];
- ss = min(ss, mat[i][j]);
- }
- }
- if(k == 1) {
- cout << ss << endl;
- return 0;
- }
- int K = k;
- k *= k;
- smaller_values.insert(mat[0][0]);
- for(int i = 0; i < K; i++) {
- for(int j = 0; j < K; j++) {
- if(i == 0 and j == 0) continue;
- insert_value(mat[i][j]);
- }
- }
- ll result = *smaller_values.rbegin();
- int i1 = 0, i2 = K - 1;
- int j1 = 0, j2 = K - 1;
- int dir = 1;
- while(i2 < n) {
- if(dir == 1) {
- result = min(result, *smaller_values.rbegin());
- if(j2 + 1 < n) {
- for(int i = i1; i <= i2; i++) {
- remove_element(mat[i][j1]);
- }
- j1++;
- j2++;
- for(int i = i1; i <= i2; i++) {
- insert_value(mat[i][j2]);
- }
- result = min(result, *smaller_values.rbegin());
- }
- else {
- dir = -1;
- for(int j = j1; j <= j2; j++) {
- remove_element(mat[i1][j]);
- }
- i1++;
- i2++;
- if(i2 < n) {
- for(int j = j1; j <= j2; j++) {
- insert_value(mat[i2][j]);
- }
- result = min(result, *smaller_values.rbegin());
- }
- }
- }
- else {
- result = min(result, *smaller_values.rbegin());
- if(j1 - 1 >= 0) {
- for(int i = i1; i <= i2; i++) {
- remove_element(mat[i][j2]);
- }
- j1--;
- j2--;
- for(int i = i1; i <= i2; i++) {
- insert_value(mat[i][j1]);
- }
- }
- else {
- dir = 1;
- for(int j = j1; j <= j2; j++) {
- remove_element(mat[i1][j]);
- }
- i1++;
- i2++;
- if(i2 < n) {
- for(int j = j1; j <= j2; j++) {
- insert_value(mat[i2][j]);
- }
- result = min(result, *smaller_values.rbegin());
- }
- }
- }
- }
- cout << result << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement