Submission #163415

#	Time	Username	Problem	Language	Result	Execution time	Memory
163415		iefnah06	The Kingdom of JOIOI (JOI17_joioi)	C++11	100 / 100	260 ms	93840 KiB

joioi

#include <bits/stdc++.h>
using namespace std;

namespace from_kczno1 {
const int ch_top=4e6*11+1e6;
char ch[ch_top],*now_r=ch-1;
#define c (*now_r)
#define gc (*++now_r)
int read()
{
    while(gc<'-');
    int x=c-'0';
    while(gc>='0')x=x*10+c-'0';
    return x;
}
#undef gc
#undef c
}
using namespace from_kczno1;

const int INF = 1.1e9;

const int MAXX = 2010;
const int MAXY = 2010;
short X, Y;
int A[MAXX][MAXY];

int gmi, gma;
int mi, ma;

bool is_good(int v) {
	int lhi = gmi + v;
	int rlo = gma - v;
	short prv = Y;
	for (short x = 0; x < X; x++) {
		short cur = 0;
		while (cur < prv && A[x][cur] <= lhi) {
			cur++;
		}
		for (short i = cur; i < Y; i++) {
			if (A[x][i] < rlo) return false;
		}
		prv = cur;
	}
	return true;
}

// keep the upper bound

void go() {
	mi = -1;
	while (ma - mi > 1) {
		int md = (mi + ma) / 2;
		if (is_good(md)) {
			ma = md;
		} else {
			mi = md;
		}
	}
}

int main() {
	fread(ch,1,ch_top,stdin);
	X = read(), Y = read();
	gmi = INF, gma = -INF;
	for (short x = 0; x < X; x++) {
		for (short y = 0; y < Y; y++) {
			A[x][y] = read();
			gmi = min(gmi, A[x][y]);
			gma = max(gma, A[x][y]);
		}
	}
	
	ma = gma - gmi;
	go();
	for (short x = 0; x < X; x++) {
		reverse(A[x], A[x] + Y);
	}
	go();
	for (short y = 0; y < Y; y++) {
		for (short x = 0; x < X / 2; x++) {
			swap(A[x][y], A[X - 1 - x][y]);
		}
	}
	go();
	for (short x = 0; x < X; x++) {
		reverse(A[x], A[x] + Y);
	}
	go();
	cout << ma << '\n';

	return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:63:7: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  fread(ch,1,ch_top,stdin);
  ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40