This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |