Submission #26929

#	Time	Username	Problem	Language	Result	Execution time	Memory
26929		kajebiii	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	3089 ms	123784 KiB

joioi

#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, int> pli;
typedef tuple<int, int, int> ti;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 2e3 + 10;

int H, W, Nr[MAX_N][MAX_N], Memo[MAX_N][MAX_N];;
vector<ti> Ts;
vector<int> Co;
int solve() {
	int cN = SZ(Co);
	int minV, mx, my; tie(minV, mx, my) = Ts[0];
	int maxV = get<0>(Ts.back()), tempL = -1;
	for(int i=0; i<=mx; i++) for(int j=0; j<=my; j++) tempL = max(tempL, Nr[i][j]);
	int res = INF;
	for(int l=tempL-minV, r=maxV-minV; l<=r;) {
		int m = (l+r) >> 1;
		int last = W-1;
		int mxV = -1, mnV = INF;
		for(int i=0, now; i<H; i++) {
			now = -1;
			while(now+1 <= last && Nr[i][now+1] - minV <= m) now++;
			last = now;
			for(int j=now+1; j<W; j++) mxV = max(mxV, Nr[i][j]), mnV = min(mnV, Nr[i][j]);
		}
		if(mxV - mnV <= m) res = m, r = m-1; else l = m+1;
	}
//	printf("res : [%d]\n\n", res);
	return res;
}
int main() {
	cin >> H >> W;
	for(int i=0; i<H; i++) for(int j=0; j<W; j++) 
		scanf("%d", &Nr[i][j]), Ts.push_back(ti(Nr[i][j], i, j)), Co.push_back(Nr[i][j]);
	sort(ALL(Ts)); sort(ALL(Co)); Co.erase(unique(ALL(Co)), Co.end());

	int ans = INF;
	for(int o0=0; o0<2; o0++) {
		for(int o1=0; o1<2; o1++) {
			ans = min(ans, solve());
			for(int i=0; i<H; i++) for(int j=0; j<W; j++) Memo[i][j] = Nr[i][j];
			for(int i=0; i<H; i++) for(int j=0; j<W; j++) Nr[i][j] = Memo[i][W-1-j];
			for(ti &e : Ts) get<2>(e) = W-1-get<2>(e);
		}
		for(int i=0; i<H; i++) for(int j=0; j<W; j++) Memo[i][j] = Nr[i][j];
		for(int i=0; i<H; i++) for(int j=0; j<W; j++) Nr[i][j] = Memo[H-1-i][j];
		for(ti &e : Ts) get<1>(e) = H-1-get<1>(e);
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'int solve()':
joioi.cpp:23:6: warning: unused variable 'cN' [-Wunused-variable]
  int cN = SZ(Co);
      ^
joioi.cpp: In function 'int main()':
joioi.cpp:46:83: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &Nr[i][j]), Ts.push_back(ti(Nr[i][j], i, j)), Co.push_back(Nr[i][j]);
                                                                                   ^

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