oj.uz

Submission #157147

# Submission time Handle Problem Language Result Execution time Memory
157147 2019-10-09T17:40:23 Z staniewzki The Kingdom of JOIOI (JOI17_joioi) C++14
100 / 100
 2233 ms 55012 KB 
#include<bits/stdc++.h>
using namespace std;

ostream& operator<<(ostream &out, string str) {
	for(char c : str) out << c;
	return out;
}
 
template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
	return out << "(" << p.first << ", " << p.second << ")";
}
 
template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
	out << "{";
	for(auto it = a.begin(); it != a.end(); it = next(it))
		out << (it != a.begin() ? ", " : "") << *it;
	return out << "}";
}
 
void dump() { cerr << "\n"; }
template<class T, class... Ts> void dump(T a, Ts... x) {
	cerr << a << ", ";
	dump(x...);
}
 
#ifdef DEBUG
#  define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#  define debug(...) false
#endif
 
#define REP(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define ST first
#define ND second
 
template<class T> int size(T && a) { return a.size(); }

using LL = long long;
using PII = pair<int, int>;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, m;
	cin >> n >> m;

	vector<vector<int>> a(n, vector<int>(m));
	int mx = 0, mn = 1e9;
	REP(i, n) REP(j, m) {
		cin >> a[i][j];
		mx = max(mx, a[i][j]);
		mn = min(mn, a[i][j]);
	}

	debug(mn, mx);
	auto check = [&](int h) {
		debug(h);
		REP(t, 4) {
			int l = 0, r = m;
			bool ok = true;
			REP(i, n) debug(i, a[i]);
			REP(i, n) {
				l = 0;
				REP(j, m) {
					if(a[i][j] - mn > h && mx - a[i][j] > h) ok = false;
					if(a[i][j] - mn <= h && mx - a[i][j] > h) l = max(l, j + 1);
					if(a[i][j] - mn > h && mx - a[i][j] <= h) r = min(r, j);
				}
				if(l > r) ok = false;
			}
			if(ok) return true;
			reverse(a.begin(), a.end());
			if(t % 2 == 0) REP(i, n) reverse(a[i].begin(), a[i].end());
		}
		return false;
	};
	
	int l = 0, r = mx - mn;
	while(l < r) {
		int m = (l + r) / 2;
		if(check(m))
			r = m;
		else
			l = m + 1;
	}

	cout << l << "\n";
}

Compilation message

joioi.cpp: In function 'int main()':
joioi.cpp:57:15: warning: statement has no effect [-Wunused-value]
  debug(mn, mx);
               ^
joioi.cpp: In lambda function:
joioi.cpp:59:11: warning: statement has no effect [-Wunused-value]
   debug(h);
           ^
joioi.cpp:63:28: warning: statement has no effect [-Wunused-value]
    REP(i, n) debug(i, a[i]);
                            ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 7 ms 504 KB Output is correct
17 Correct 14 ms 784 KB Output is correct
18 Correct 13 ms 888 KB Output is correct
19 Correct 16 ms 760 KB Output is correct
20 Correct 16 ms 760 KB Output is correct
21 Correct 16 ms 888 KB Output is correct
22 Correct 16 ms 888 KB Output is correct
23 Correct 20 ms 888 KB Output is correct
24 Correct 14 ms 888 KB Output is correct
25 Correct 26 ms 888 KB Output is correct
26 Correct 16 ms 888 KB Output is correct
27 Correct 16 ms 888 KB Output is correct
28 Correct 17 ms 888 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 7 ms 504 KB Output is correct
17 Correct 14 ms 784 KB Output is correct
18 Correct 13 ms 888 KB Output is correct
19 Correct 16 ms 760 KB Output is correct
20 Correct 16 ms 760 KB Output is correct
21 Correct 16 ms 888 KB Output is correct
22 Correct 16 ms 888 KB Output is correct
23 Correct 20 ms 888 KB Output is correct
24 Correct 14 ms 888 KB Output is correct
25 Correct 26 ms 888 KB Output is correct
26 Correct 16 ms 888 KB Output is correct
27 Correct 16 ms 888 KB Output is correct
28 Correct 17 ms 888 KB Output is correct
29 Correct 1034 ms 37380 KB Output is correct
30 Correct 1236 ms 36440 KB Output is correct
31 Correct 1622 ms 39268 KB Output is correct
32 Correct 1047 ms 39392 KB Output is correct
33 Correct 817 ms 34224 KB Output is correct
34 Correct 1327 ms 39388 KB Output is correct
35 Correct 1450 ms 54888 KB Output is correct
36 Correct 1129 ms 47852 KB Output is correct
37 Correct 2233 ms 55012 KB Output is correct