Submission #305237

#	Time	Username	Problem	Language	Result	Execution time	Memory
305237		pit4h	The Kingdom of JOIOI (JOI17_joioi)	C++14	60 / 100	4082 ms	142628 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e12+1;
bool possible(vector<vector<ll>> grid, ll M, ll L, ll R) {
	int h = grid.size(), w = grid[0].size();
	vector<vector<bool>> dp(h, vector<bool>(w+1));
	dp[0][0] = 1;
	for(int i=0; i<h; ++i) {
		ll mx = L;
		if(i!=0) {
			dp[i][0] = dp[i-1][0];
		}
		for(int j=0; j<w; ++j) {
			mx = max(mx, grid[i][j]);
			if(i!=0) {
				dp[i][j+1] = dp[i][j+1] | dp[i-1][j+1];
			}
			dp[i][j+1] = dp[i][j+1] | dp[i][j];
			if(mx-L > M) dp[i][j+1] = 0;
		}
		ll mini = R;
		for(int j=w; j>=0; --j) {
			if(R-mini > M) dp[i][j] = 0;
			if(j-1>=0) mini = min(mini, grid[i][j-1]);
		}
	}
	bool res = 0;
	for(int i=0; i<w; ++i) {
		if(dp[h-1][i+1]) res = 1;
	}
	return res;
}
ll solve(vector<vector<ll>> grid) {
	int h = grid.size(), w = grid[0].size();
	ll L = INF, R = 0;
	for(int i=0; i<h; ++i) {
		for(int j=0; j<w; ++j) {
			L = min(L, grid[i][j]);
			R = max(R, grid[i][j]);
		}
	}
	ll lo = 0, hi = R - L;
	ll res = INF;
	while(lo<=hi) {
		ll M = (lo+hi)/2;
		if(possible(grid, M, L, R)) {
			hi = M - 1;	
			res = M;
		}
		else {
			lo = M + 1;
		}
	}
	return res;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int h, w; cin>>h>>w;
	vector<vector<ll>> grid(h, vector<ll>(w));
	for(int i=0; i<h; ++i) {
		for(int j=0; j<w; ++j) {
			cin>>grid[i][j];
		}
	}
	ll ans = INF;
	auto G = grid;
	ans = min(ans, solve(G));
	reverse(G.begin(), G.end());
	ans = min(ans, solve(G));
	for(int i=0; i<h; ++i) {
		reverse(G[i].begin(), G[i].end());	
	}
	ans = min(ans, solve(G));
	reverse(G.begin(), G.end());
	ans = min(ans, solve(G));	
	cout<<ans;
}

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