Submission #1143787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143787		SmuggingSpun	The Kingdom of JOIOI (JOI17_joioi)	C++20	15 / 100	36 ms	1096 KiB

joioi

#include<bits/stdc++.h>
#define taskname "C"
using namespace std;
const int INF = 1e9;
template<class T>void minimize(T& a, T b){
	if(a > b){
		a = b;
	}
}
template<class T>void maximize(T& a, T b){
	if(a < b){
		a = b;
	}
}
int n, m;
namespace sub1{
	void solve(){
		vector<vector<int>>a(n, vector<int>(m));
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				cin >> a[i][j];
			}
		}
		int ans = INF;
		vector<int>current;
		auto play = [&] (auto&& self, int p) -> void{
			if(p == n){
				if(current[0] > 0 && current[n - 1] < m){
					int a_max = 0, b_max = 0, a_min = INF, b_min = INF;
					for(int i = 0; i < n; i++){
						for(int j = 0; j < current[i]; j++){
							maximize(a_max, a[i][j]);
							minimize(a_min, a[i][j]);
						}
						for(int j = current[i]; j < m; j++){
							maximize(b_max, a[i][j]);
							minimize(b_min, a[i][j]);
						}
					}
					minimize(ans, max(a_max - a_min, b_max - b_min));
				}
				return;	
			}
			for(int i = (current.empty() ? m : current.back()); i > -1; i--){
				current.emplace_back(i);
				self(self, p + 1);
				current.pop_back();
			}
		};
		play(play, 0);
		reverse(a.begin(), a.end());
		play(play, 0);
		cout << ans;
	}
}
namespace sub23{
	void solve(){
		vector<vector<int>>a(n + 1, vector<int>(m + 1)), pref_min(n + 1, vector<int>(m + 1)), suf_max(n + 1, vector<int>(m + 2)), suf_min(n + 1, vector<int>(m + 2));
		int x = 1, y = 1;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				cin >> a[i][j];
				if(a[i][j] > a[x][y]){
					x = i;
					y = j;
				}
			}
		}
		int ans = INF;
		auto eval = [&] (int min_value){
			int other_max = 0, other_min = INF;
			for(int i = 1, pre = m; i <= n; i++){
				int low = 1, high = m, p = 0;
				while(low <= high){
					int mid = (low + high) >> 1;
					if(pref_min[i][mid] >= min_value){
						low = (p = mid) + 1;
					}
					else{
						high = mid - 1;
					}
				}
				minimize(pre, p);
				if(i == x && pre < y){
					return INF;
				}
				maximize(other_max, suf_max[i][pre + 1]);
				minimize(other_min, suf_min[i][pre + 1]);
			}
			return max(a[x][y] - min_value, max(other_max - other_min, 0));
		};
		auto work = [&] (){
			for(int i = 1; i <= n; i++){
				suf_max[i][m + 1] = -(suf_min[i][m + 1] = pref_min[i][0] = INF);
				for(int j = 1; j <= m; j++){
					pref_min[i][j] = min(pref_min[i][j - 1], a[i][j]);
				}
				for(int j = m; j > 0; j--){
					suf_min[i][j] = min(suf_min[i][j + 1], a[i][j]);
					suf_max[i][j] = max(suf_max[i][j + 1], a[i][j]);
				}
			}
			for(int iter = 0, low = 0, high = a[x][y]; iter < 80; iter++){
				int mid_1 = low + (high - low) / 3, mid_2 = high - (high - low) / 3, f1 = eval(mid_1), f2 = eval(mid_2);
				minimize(ans, min(f1, f2));
				if(f1 > f2){
					low = mid_1;
				}
				else{
					high = mid_2;
				}
			}
		};
		work();
		reverse(a.begin() + 1, a.end());
		x = n - x + 1;
		work();
		for(int i = 1; i <= n; i++){
			reverse(a[i].begin() + 1, a[i].end());
		}
		y = n - y + 1;
		work();
		reverse(a.begin() + 1, a.end());
		x = n - x + 1;
		work();
		cout << ans;
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> m;
	if(n <= 10 && m <= 10){
		sub1::solve();
	}
	else{
		sub23::solve();
	}
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:132:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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