#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
const int maxn = 1e3 + 10;
int mat[maxn][maxn];
int opt[maxn][maxn];
vector<pair<int, int>> dir = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
int n, m;
bool check(int x, int y) {
return x >= 0 && y >= 0 && x < n && y < m;
}
int solve() {
int ans = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int i2 = 0; i2 < n; i2++) {
for (int j2 = 0; j2 < m; j2++) {
if (mat[i][j] <= mat[i2][j2])
ans = max(ans, mat[i][j] - mat[i2][j2] - abs(i - i2) - abs(j - j2) - 1);
}
}
}
}
return ans;
}
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;
bool f = 0;
set<pair<pair<int, int>, pair<int, int>>> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> mat[i][j];
if (mat[i][j] != mat[0][0])
f = 1;
opt[i][j] = -1;
q.insert({{mat[i][j], -1}, {i, j}});
}
}
while (!q.empty()) {
auto v = *q.rbegin();
q.erase(v);
int x = v.y.x;
int y = v.y.y;
// cout << x << ' ' << y << ' ' << v.x.y << endl;
for (auto el : dir) {
int x2 = el.x + x;
int y2 = el.y + y;
if (!check(x2, y2) || mat[x2][y2] > mat[x][y])
continue;
// cout << x2 << ' ' << y2 << endl;
if (opt[x2][y2] < opt[x][y] + mat[x][y] - mat[x2][y2] - 1) {
q.erase({{mat[x2][y2], opt[x2][y2]}, {x2, y2}});
opt[x2][y2] = max(opt[x2][y2], opt[x][y] + mat[x][y] - mat[x2][y2] - 1);
q.insert({{mat[x2][y2], opt[x2][y2]}, {x2, y2}});
ans = max(ans, opt[x2][y2]);
}
}
}
// if (ans == -1 && f)
// assert(0);
cout << solve();
return 0;
}
Compilation message
maxcomp.cpp: In function 'int main()':
maxcomp.cpp:58:7: warning: variable 'f' set but not used [-Wunused-but-set-variable]
58 | bool f = 0;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
