제출 #68252

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68252		Nurlykhan	The Kingdom of JOIOI (JOI17_joioi)	C++17	60 / 100	1633 ms	263168 KiB

joioi

#include <bits/stdc++.h>

#define pb push_back
#define all(v) v.begin(), v.end()
#define sz(v) int(v.size())
#define pii pair<int, int>
#define mp make_pair
#define f first
#define ll long long
#define ld long double
#define s second
#define vec vector<int>

using namespace std;

const int N = (int) 2e3 + 10;
const int M = (int) 2018 * 2018;
const int K = (int) 8;
const int INF = (int) 1e9 + 7;
const int mod = (int) 998244353;
const ld EPS = (ld) 1e-9;
const ll LINF = (ll) 1e18;

int n, m;
vector<vector<int> > a;
pii mx[K];
int pref[K][N][N], suff_max[K][N][N], suff_min[K][N][N];
vector<vector<vector<int> > > v;

void precalc(int id) {
	// global max
	vector<vector<int> > a = v[id];
	int cur_n = sz(a);
	int cur_m = sz(a[0]);
	for (int i = 0; i < cur_n; i++) {
		for (int j = 0; j < cur_m; j++) {
			if (a[mx[id].f][mx[id].s] < a[i][j]) {
				mx[id] = mp(i, j);
			}
		}
	}
	for (int i = 0; i < cur_n; i++) {
		for (int j = 0; j < cur_m; j++) {
			pref[id][i][j] = a[i][j];
			if (j > 0) 
				pref[id][i][j] = min(pref[id][i][j], pref[id][i][j - 1]);
		}
		suff_min[id][i][cur_m] = INF;
		suff_max[id][i][cur_m] = 0;
		for (int j = cur_m - 1; j >= 0; j--) {
			suff_max[id][i][j] = max(a[i][j], suff_max[id][i][j + 1]);
			suff_min[id][i][j] = min(a[i][j], suff_min[id][i][j + 1]);
		}
	}
}

bool solve(int id, int diff) {
	int cur_n = sz(v[id]);
	int cur_m = sz(v[id][0]);
	int ptr = cur_m - 1;
	int max_val = v[id][mx[id].f][mx[id].s];
	int mn = INF, mx = 0;
	for (int i = 0; i < cur_n; i++) {
		while (ptr >= 0 && max_val > diff + pref[id][i][ptr]) {
			ptr--;
		}
		mn = min(mn, suff_min[id][i][ptr + 1]);
		mx = max(mx, suff_max[id][i][ptr + 1]);
	}
	return mx - mn <= diff;
}

void mirror() {
	for (int i = 0; i < n / 2; i++) {
		for (int j = 0; j < m; j++) {
			swap(a[i][j], a[n - 1 - i][j]);
		}
	}
}

int b[N][N];

void rotate() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			b[j][n - i - 1] = a[i][j];
		}
	}
	swap(n, m);
	a.clear();
	for (int i = 0; i < n; i++) {
		a.pb(vector<int>(m));
		for (int j = 0; j < m; j++) {
			a[i][j] = b[i][j];
		}
	}
}

bool ok(int diff) {
	for (int i = 0; i < sz(v); i++) {
		if (solve(i, diff))
			return true;
	}
	return false;
}

int main() {
	#ifdef sony
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
	srand(time(0));
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		a.pb(vector<int>(m));
		for (int j = 0; j < m; j++) {
			scanf("%d", &a[i][j]);
		}
	}
	for (int i = 0; i < 4; i++) {
		v.pb(a);
		mirror();
		v.pb(a);
		mirror();
		rotate();
	}
	for (int i = 0; i < sz(v); i++) {
		precalc(i);
	}
	int l = 1, r = INF;
	int ans;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (ok(mid)) {
			r = mid - 1;
			ans = mid;
		} else {
			l = mid + 1;
		}
	}
	cout << ans;
	return 0;	
}

컴파일 시 표준 에러 (stderr) 메시지

joioi.cpp: In function 'int main()':
joioi.cpp:117:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~
joioi.cpp:141:7: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout << ans;
  ~~~~~^~~~~~

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