Submission #360110

#	Time	Username	Problem	Language	Result	Execution time	Memory
360110		Poimidorka	Maxcomp (info1cup18_maxcomp)	C++17	100 / 100	158 ms	16748 KiB

maxcomp

#include <random>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <queue>
#include <string>
#include <algorithm>
#include <tuple>
#include <cassert>


using namespace std;


#define x first
#define y second
//#define int long long


#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,sse4,tune=native")
#pragma GCC optimize("unroll-loops")


const int maxn = 1e3 + 10;


int mat[maxn][maxn];
int d1[maxn][maxn];
int n, m;


signed main() {
#ifdef LC
	assert(freopen("input.txt", "r", stdin));
#endif
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	int ans = -1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			cin >> mat[i][j];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			d1[i][j] = mat[i][j] + i + j;
			if (i)
				d1[i][j] = max(d1[i][j], d1[i - 1][j]);
			if (j)
				d1[i][j] = max(d1[i][j], d1[i][j - 1]);			
			ans = max(ans, d1[i][j] - mat[i][j] - i - j - 1);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = m - 1; j >= 0; j--) {
			d1[i][j] = mat[i][j] + i - j;
			if (i)
				d1[i][j] = max(d1[i][j], d1[i - 1][j]);
			if (j != m - 1)
				d1[i][j] = max(d1[i][j], d1[i][j + 1]);			
			ans = max(ans, d1[i][j] - mat[i][j] - i + j - 1);
		}
	}
	for (int i = n - 1; i >= 0; i--) {
		for (int j = 0; j < m; j++) {
			d1[i][j] = mat[i][j] - i + j;
			if (i != n - 1)
				d1[i][j] = max(d1[i][j], d1[i + 1][j]);
			if (j)
				d1[i][j] = max(d1[i][j], d1[i][j - 1]);
			ans = max(ans, d1[i][j] - mat[i][j] + i - j - 1);
		}
	}
	// for (int i = 0; i < n; i++) {
	// 	for (int j = 0; j < m; j++)
	// 		cout << d1[i][j] << ' ';
	// 	cout << '\n';
	// }
	for (int i = n - 1; i >= 0; i--) {
		for (int j = m - 1; j >= 0; j--) {
			d1[i][j] = mat[i][j] - i - j;
			if (i != n - 1)
				d1[i][j] = max(d1[i][j], d1[i + 1][j]);
			if (j != m - 1)
				d1[i][j] = max(d1[i][j], d1[i][j + 1]);			
			ans = max(ans, d1[i][j] - mat[i][j] + i + j - 1);
			// cout << d1[i][j] << ' ';
		}
		// cout << endl;
	}
	cout << ans;
	return 0;
}

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