oj.uz

Submission #496897

# Submission time Handle Problem Language Result Execution time Memory
496897 2021-12-22T06:12:50 Z Nalrimet Maxcomp (info1cup18_maxcomp) C++17
15 / 100
 500 ms 332 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Execution timed out 1087 ms 332 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Execution timed out 1087 ms 332 KB Time limit exceeded
10 Halted 0 ms 0 KB -