Submission #305250

#	Time	Username	Problem	Language	Result	Execution time	Memory
305250		pit4h	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	658 ms	102396 KiB

joioi

#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
using ll = int;
const ll INF = 1e9+1;
int value(pair<int, int> x) {
	return max(x.st, x.nd);
}
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]);
		}
	}
	vector<vector<pair<int, int>>> dp(h+1, vector<pair<int, int>>(w+1));
	for(int i=1; i<=h; ++i) {
		int mx = L;
		dp[i][0] = dp[i-1][0];
		for(int j=1; j<=w; ++j) {
			mx = max(mx, grid[i-1][j-1]);
			dp[i][j] = dp[i-1][j];
			if(value(dp[i][j-1]) < value(dp[i][j])) {
				dp[i][j] = dp[i][j-1];
			}
			dp[i][j].st = max(dp[i][j].st, mx-L);
		}
		int mini = R;
		for(int j=w; j>=0; --j) {
			dp[i][j].nd = max(dp[i][j].nd, R-mini);
			if(j-1>=0) {
				mini = min(mini, grid[i-1][j-1]);
			}
		}
	}
	int res = INF;
	for(int i=1; i<=w; ++i) {
		res = min(res, value(dp[h][i]));
	}
	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: 40 / 40