Submission #46790

#	Time	Username	Problem	Language	Result	Execution time	Memory
46790		jun6873	Maxcomp (info1cup18_maxcomp)	C++11	100 / 100	241 ms	68572 KiB

maxcomp

#include <bits/stdc++.h>
using namespace std;

int h, w, a[1004][1004], mx[1004][1004];

int solve() {
	for (int i=0; i<=h; i++) for (int j=0; j<=w; j++) mx[i][j] = -2e9;
	int ret = -2e9;
	for (int i=1; i<=h; i++) for (int j=1; j<=w; j++) {
		int k = i + j - a[i][j];
		mx[i][j] = max({mx[i-1][j], mx[i][j-1], k});
		ret = max(ret, mx[i][j] - k - 1);
	}
	return ret;
}

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

	cin >> h >> w;
	for (int i=1; i<=h; i++) for (int j=1; j<=w; j++)
		cin >> a[i][j];

	int ans = solve();
	for (int i=1; i<=h; i++) for (int j=1; j<=w/2; j++) swap(a[i][j], a[i][w-j+1]);
	ans = max(ans, solve());
	for (int i=1; i<=h/2; i++) for (int j=1; j<=w; j++) swap(a[i][j], a[h-i+1][j]);
	ans = max(ans, solve());
	for (int i=1; i<=h; i++) for (int j=1; j<=w/2; j++) swap(a[i][j], a[i][w-j+1]);
	ans = max(ans, solve());

	cout << ans << "\n";
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40