Submission #923436

#	Time	Username	Problem	Language	Result	Execution time	Memory
923436		Gromp15	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	808 ms	55124 KiB

joioi

#include <bits/stdc++.h>
#define ll long long
#define ar array
#define db double
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
const int INF = 1e9;
void test_case() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> a(n+1, vector<int>(m+1));
	int mx = 0, mn = INF;
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { 
		cin >> a[i][j];
		ckmax(mx, a[i][j]);
		ckmin(mn, a[i][j]);
	}
	vector<ar<int, 3>> vals(8);
	for (int i = 0; i < 8; i++) {
		vals[i][0] = i >> 2 & 1;
		vals[i][1] = i >> 1 & 1;
		vals[i][2] = i & 1;
	}
	int ans = mx - mn;
	// give the max/min to who
	for (int A = 0; A < 2; A++) {
		// !A = left has max, right has min
		// A = left has min, right has max
		vector<vector<int>> dp(8, vector<int>(m+1, INF));
		auto conv = [](int vis_left, int vis_right, int order) {
			return (vis_left << 2) + (vis_right << 1) + order;
		};
		// order = 0 ==> going right
		dp[conv(0, 0, 0)][0] = 0;
		dp[conv(0, 0, 1)][m] = 0;
		for (int i = 1; i <= n; i++) {
			vector<vector<int>> dp2(8, vector<int>(m+1, INF));
			vector<bool> vleft(m+1), vright(m+1);
			vector<int> pref(m+1, !A ? INF : -1), suff(m+1, !A ? -1 : INF);
			for (int j = 1; j <= m; j++) {
				vleft[j] = (a[i][j] == (A ? mn : mx)) || vleft[j-1];
				if (!A) pref[j] = min(a[i][j], pref[j-1]);
				else pref[j] = max(a[i][j], pref[j-1]);
			}
			for (int j = m-1; j >= 0; j--) {
				vright[j] = (a[i][j+1] == (A ? mx : mn)) || vright[j+1];
				if (!A) suff[j] = max(a[i][j+1], suff[j+1]);
				else suff[j] = min(a[i][j+1], suff[j+1]);
			}
			if (!A) { // maximize for left, minimize for right
				pref[0] = mx, suff[m] = mn;
			}
			else {
				pref[0] = mn, suff[m] = mx;
			}
			for (int j = 0; j < 8; j++) {
				const auto& [vis_left, vis_right, order] = vals[j];
				vector<int> pref_mn(m+1), suff_mn(m+1);
				for (int k = 0; k <= m; k++) {
					pref_mn[k] = min(dp[j][k], k ? pref_mn[k-1] : INF);
				}
				for (int k = m; k >= 0; k--) {
					suff_mn[k] = min(dp[j][k], k+1 <= m ? suff_mn[k+1] : INF);
				}
				for (int k = 0; k <= m; k++) {
					auto calc = [&]() {
						if (!A) return max(mx - pref[k], suff[k] - mn);
						return max(pref[k] - mn, mx - suff[k]);
					};
					if (!order) {
						ckmin(dp2[conv(vis_left | vleft[k], vis_right | vright[k], order)][k], max(pref_mn[k], calc()));
					}
					else {
						ckmin(dp2[conv(vis_left | vleft[k], vis_right | vright[k], order)][k], max(suff_mn[k], calc()));
					}
				}
			}
			swap(dp, dp2);
		}
		for (int i = 0; i < 2; i++) {
			ckmin(ans, *min_element(all(dp[conv(1, 1, i)])));
		}
	}
	cout << ans << '\n';


}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
//    cin >> t;
    while (t--) test_case();
}

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