Submission #1142786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142786		Muhammet	Maxcomp (info1cup18_maxcomp)	C++20	100 / 100	74 ms	8264 KiB

maxcomp

#include "bits/stdc++.h"

using namespace std;

int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	vector <vector <int>> a(n+1, vector <int> (m+1));
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
		}
	}
	vector <vector <int>> dp(n+2, vector <int> (m+2, 1e9));
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			dp[i][j] = min(dp[i][j], min(a[i][j], dp[i][j-1] + 1));
		}
		for(int j = m; j >= 1; j--){
			dp[i][j] = min(dp[i][j], min(a[i][j], dp[i][j+1] + 1));
		}
	}
	for(int j = 1; j <= m; j++){
		for(int i = 1; i <= n; i++){
			dp[i][j] = min(dp[i][j], dp[i-1][j] + 1);
		}
		for(int i = n; i >= 1; i--){
			dp[i][j] = min(dp[i][j], dp[i+1][j] + 1);
		}
	}
	int ans = -1;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			ans = max(ans, a[i][j] - dp[i][j]);
		}
	}
	cout << ans-1;
}

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