oj.uz

Submission #305240

# Submission time Handle Problem Language Result Execution time Memory
305240 2020-09-22T19:04:06 Z pit4h The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 1 ms 384 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = int;
const ll INF = 1e9+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 = (R-L)/2, 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -