Submission #1143039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143039		tkm_algorithms	Maxcomp (info1cup18_maxcomp)	C++20	100 / 100	113 ms	16184 KiB

maxcomp

/**
*    In the name of Allah
*    We are nothing and you're everything
*    author: najmuddin
**/
 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
	
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
#define int ll
 
const char nl = '\n';
const int N = 1e8+5;
//const int inf = 1e18;
const int mod = 1e9+7;

void solve() {
	int ans = -1;
	
	int n, m; cin >> n >> m;
	
	vector<vector<int>> dp(n+1, vector<int> (m+1));

	vector<vector<int>> a(n, vector<int> (m));
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)cin >> a[i][j];
		
	// vpravo
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j) {
			dp[i][j] = a[i][j]+1;
			if (j > 0)dp[i][j] = min(dp[i][j-1]+1, dp[i][j]);
		}
		
	//vlevo
	for (int i = 0; i < n; ++i) 
		for (int j = m-1; j >= 0; --j) {
			dp[i][j] = min(dp[i][j], a[i][j]+1);
			if (j < m-1)dp[i][j] = min(dp[i][j], dp[i][j+1]+1);
		}
	
	//vverh
	for (int j = 0; j < m; ++j)
		for (int i = n-1; i >= 0; --i) {
			dp[i][j] = min(dp[i][j], a[i][j]+1);
			if (i < n-1)dp[i][j] = min(dp[i][j], dp[i+1][j]+1);
		}
		
	//vniz
	
	for (int j = 0; j < m; ++j) {
		for (int i = 0; i < n; ++i) {
			dp[i][j] = min(dp[i][j], a[i][j]+1);
			if (i > 0)
				dp[i][j] = min(dp[i][j], dp[i-1][j]+1);
		}
	}
	
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			ans = max(ans, a[i][j]-dp[i][j]);
	cout << ans;
}
 
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
	
	int t = 1;
	//cin >> t;
	
	while (t--) {
		solve();
	}
    return 0;
}

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