Submission #496897

#	Time	Username	Problem	Language	Result	Execution time	Memory
496897		Nalrimet	Maxcomp (info1cup18_maxcomp)	C++17	15 / 100	1087 ms	332 KiB

maxcomp

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define F first
#define S second

using namespace std;

const int N = 1e2 + 5;
const int inf = 1e9+7;

int n, m, dist, a[N][N], cur, mx, ans = -inf;
bool used[N][N];

void rec(int i, int j, int mn){
    dist++;
    used[i][j] = 1;
    if(cur <= dist) {used[i][j] = 0;dist--;return;}
    if(cur >= mn + dist){
        cur = mn + dist;
    }
    if(a[i][j + 1] <= mx && !used[i][j + 1]){
        rec(i, j + 1, min(mn, a[i][j + 1]));
    }
    if(a[i][j - 1] <= mx && !used[i][j - 1]){
        rec(i, j - 1, min(mn, a[i][j - 1]));
    }
    if(a[i + 1][j] <= mx && !used[i + 1][j]){
        rec(i + 1, j, min(mn, a[i + 1][j]));
    }
    if(a[i - 1][j] <= mx && !used[i - 1][j]){
        rec(i - 1, j, min(mn, a[i - 1][j]));
    }
    used[i][j] = 0;
    dist--;
}

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

	cin >> n >> m;

	for(int i = 1; i <= n; ++i){
        a[i][0] = inf;
        a[i][m + 1] = inf;
        for(int j = 1; j <= m; ++j){
            cin >> a[i][j];
        }
	}

	for(int j = 1; j <= m; ++j){
        a[0][j] = inf;
        a[n + 1][j] = inf;
	}

	for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
//            memset(used, 0, sizeof(used));
            if(ans >= a[i][j]) continue;
            
            mx = a[i][j];
            cur = inf;
            rec(i, j, a[i][j]);
//            cout << cur << ' ' << a[i][j] << '\n';
            ans = max(a[i][j] - cur, ans);
        }
	}

	cout << ans;

	return 0;
}

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