#ifdef LC
#include "pch.h"
#else
#include <bits/stdc++.h>
#endif
using namespace std;
using ll = long long;
#define int ll
#define all(x) x.begin(), x.end()
#define x first
#define y second
#define mp make_pair
#define mt make_tuple
const int N = 1 << 10;
const int INF = 1e18;
int n;
int m;
int a[N][N];
void rot() {
for (int i = 0; i < N; ++i) {
for (int j = i; j < N; ++j) {
swap(a[i][j], a[j][i]);
}
}
swap(n, m);
for (int i = 0; i < n; ++i) {
reverse(a[i], a[i] + m);
}
}
int answer = -1;
int t[2 * N];
void clear() {
fill_n(t, 2 * N, INF);
}
void update(int i, int v) {
i += N;
t[i] = min(t[i], v);
for (i /= 2; i > 0; i /= 2) {
t[i] = min(t[i + i], t[i + i + 1]);
}
}
int query(int l, int r) {
int res = INF;
for (l += N, r += N; l <= r; l /= 2, r /= 2) {
if (l % 2 == 1) {
res = min(res, t[l++]);
}
if (r % 2 == 0) {
res = min(res, t[r--]);
}
}
return res;
}
void solve() {
clear();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
answer = max(answer, a[i][j] - i - j - 1 - query(0, j));
update(j, a[i][j] + i + j);
}
}
}
signed main() {
#ifdef LC
assert(freopen("input.txt", "r", stdin));
#endif
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
for (int it = 0; it < 1; ++it) {
if (it) {
rot();
}
solve();
}
cout << answer << "\n";
return 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 |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
