Submission #524088

#	Time	Username	Problem	Language	Result	Execution time	Memory
524088		maks007	Maxcomp (info1cup18_maxcomp)	C++14	100 / 100	386 ms	13252 KiB

maxcomp

#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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40