이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f3f3f3f;
struct bibit {
static const int maxn = 1e3 + 5;
int a[maxn][maxn] = {};
int n, m;
inline int lowbit(int x) { return x & (-x); }
void init(int _n, int _m) {
n = _n, m = _m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
a[i][j] = INF;
}
void add(int x, int y, int v) {
for (int i = x; i <= n; i += lowbit(i))
for (int j = y; j <= m; j += lowbit(j))
a[i][j] = min(a[i][j], v);
}
int que(int x, int y) {
int ret = INF;
for (int i = x; i > 0; i -= lowbit(i))
for (int j = y; j > 0; j -= lowbit(j))
ret = min(ret, a[i][j]);
return ret;
}
} bit;
const int maxn = 1e3 + 5;
long long G[maxn][maxn];
void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> G[i][j];
long long ans = 0;
bit.init(n, m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
ans = max(ans, G[i][j] - i - j - bit.que(i, j));
bit.add(i, j, G[i][j] - i - j);
}
bit.init(n, m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
ans = max(ans, G[i][m-j+1] - i - j - bit.que(i, j));
bit.add(i, j, G[i][m-j+1] - i - j);
}
bit.init(n, m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
ans = max(ans, G[n-i+1][j] - i - j - bit.que(i, j));
bit.add(i, j, G[n-i+1][j] - i - j);
}
bit.init(n, m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
ans = max(ans, G[n-i+1][m-j+1] - i - j - bit.que(i, j));
bit.add(i, j, G[n-i+1][m-j+1] - i - j);
}
cout << ans - 1 << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |