oj.uz

Submission #524088

# Submission time Handle Problem Language Result Execution time Memory
524088 2022-02-08T15:37:53 Z maks007 Maxcomp (info1cup18_maxcomp) C++14
100 / 100
 386 ms 13252 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define inf -1e9
 
int main(void) {
	int n, m;
	cin >> n >> m;
	
	vector <vector <int> > g(n, vector <int> (m));
	
	function <int()> get=[&]() {
		int ans = -1e9;
		vector <int> mx(m, 1e9);
		for(int i = 0; i< n; i ++) {
			for(int j = 0; j < m; j ++) {
				if(j) {
					mx[j] = min({mx[j-1], mx[j], g[i][j] - i - j});
				}else {
					mx[j] = min({mx[j], g[i][j] - i - j});
				}
			}
			for(int j = 0; j < m; j ++) {
				ans = max(ans, g[i][j] - mx[j] - 1 - i - j);
			}
		}
		return ans;
	};
	
	for(int i  = 0; i < n; i ++) {
		for(int j = 0; j < m; j ++) cin >> g[i][j];
	}
	int getmx = -1e9;
	getmx = max(getmx, get());
	for(int i = 0; i < n; i ++) {
		reverse(g[i].begin(), g[i].end());
	}
	getmx = max(getmx, get());
	for(int i = 0; i < (n >> 1); i ++) {
		for(int j = 0; j < m; j ++) {
			swap(g[n - (i + 1)][j], g[i][j]);
		}
	}
	getmx = max(getmx, get());
	for(int i = 0; i < n; i ++) {
		reverse(g[i].begin(), g[i].end());
	}
	getmx = max(getmx, get());
	cout << getmx;
	return false;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 272 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 272 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 2 ms 328 KB Output is correct
12 Correct 2 ms 280 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 1 ms 204 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 272 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 2 ms 328 KB Output is correct
15 Correct 2 ms 280 KB Output is correct
16 Correct 1 ms 300 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 367 ms 12660 KB Output is correct
19 Correct 363 ms 12660 KB Output is correct
20 Correct 362 ms 12216 KB Output is correct
21 Correct 358 ms 12680 KB Output is correct
22 Correct 367 ms 12680 KB Output is correct
23 Correct 386 ms 12676 KB Output is correct
24 Correct 377 ms 13252 KB Output is correct