Submission #173441

#	Time	Username	Problem	Language	Result	Execution time	Memory
173441		dennisstar	The Kingdom of JOIOI (JOI17_joioi)	C++11	0 / 100	2 ms	632 KiB

joioi

#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;


int H, W;
int ar[2010][2010], im[2010][2010];
int Lmn[2010][2010], Lmx[2010][2010], Rmn[2010][2010], Rmx[2010][2010];
int lb[2010];

void init() {
	for (int i=1; i<=H; i++) Lmn[i][0]=Rmn[i][W+1]=(1<<30);
	for (int i=1; i<=W; i++) Lmn[0][i]=Rmn[H+1][i]=(1<<30);
	for (int i=1; i<=H; i++) for (int j=1; j<=W; j++) {
		Lmn[i][j]=min({ar[i][j], Lmn[i-1][j], Lmn[i][j-1]});
		Lmx[i][j]=max({ar[i][j], Lmx[i-1][j], Lmx[i][j-1]});
	}
	for (int i=H; i>=1; i--) for (int j=W; j>=1; j--) {
		Rmn[i][j]=min({ar[i][j], Rmn[i+1][j], Rmn[i][j+1]});
		Rmx[i][j]=max({ar[i][j], Rmx[i+1][j], Rmx[i][j+1]});
	}
}

int f(int v, int mn) {
	int r=W;
	int rn=(1<<30), rx=0;
	for (int i=1; i<=H; i++) {
		int u=upper_bound(Lmx[i]+1, Lmx[i]+W+1, mn+v)-Lmx[i];
		r=min(r, u-1);
		rn=min(rn, Rmn[i][u]);
		rx=max(rx, Rmx[i][u]);
	}
	if (rn==(1<<30)) rn=0;
	return (rx-rn<=v?1:0);
}

int solve() {
	init();
	int mx=0, st=0, mn=Lmn[H][W];
	for (int i=H; i>=1; i--) {
		for (int j=W; j>=1; j--) if (mn==ar[i][j]) { st=max(st, j); break; }
		lb[i]=st; mx=max(mx, Lmx[i][st]);
	}
	int s=mx-mn, e=Lmx[H][W], ret;
	int ans=(1<<30);
	while (s<e) {
		int md=(s+e)/2;
		if (f(md, mn)) {
			ans=md; e=md;
		}
		else s=md+1;
	}
	return ans;
}

int main() {
	int ans;
	scanf("%d %d", &H, &W);
	for (int i=1; i<=H; i++) for (int j=1; j<=W; j++) scanf("%d", &ar[i][j]);
	ans=solve(); 
	for (int i=1; i<=H; i++) for (int j=1; j<=W; j++) im[i][j]=ar[H-i+1][W-j+1];
	for (int i=1; i<=H; i++) for (int j=1; j<=W; j++) ar[i][j]=im[i][j];
	ans=min(ans, solve());
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'int solve()':
joioi.cpp:53:28: warning: unused variable 'ret' [-Wunused-variable]
  int s=mx-mn, e=Lmx[H][W], ret;
                            ^~~
joioi.cpp: In function 'int main()':
joioi.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &H, &W);
  ~~~~~^~~~~~~~~~~~~~~~~
joioi.cpp:68:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1; i<=H; i++) for (int j=1; j<=W; j++) scanf("%d", &ar[i][j]);
                                                    ~~~~~^~~~~~~~~~~~~~~~~

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