This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define int long long
using namespace std;
main(){
int n , m , ans = 0;
cin >> n >> m;
vector<vector<int>> a(n + 1 , vector<int>(m + 1)) , mx(n + 2 , vector<int>(m + 2));
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
cin >> a[i][j];
}
}
auto Reset = [&](){
for(int i = 0;i <= n + 1;i ++){
for(int j = 0;j <= m + 1;j ++){
mx[i][j] = -1e16;
}
}
};
Reset();
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
mx[i][j] = max({mx[i - 1][j] , mx[i][j - 1] , i + j - a[i][j]});
ans = max(ans , a[i][j] - i - j + mx[i][j]);
}
}
Reset();
for(int i = 1;i <= n;i ++){
for(int j = m;j >= 1;j --){
mx[i][j] = max({mx[i - 1][j] , mx[i][j + 1] , i - j - a[i][j]});
ans = max(ans , a[i][j] - i + j + mx[i][j]);
}
}
Reset();
for(int i = n;i >= 1;i --){
for(int j = 1;j <= m;j ++){
mx[i][j] = max({mx[i + 1][j] , mx[i][j - 1] , -i + j - a[i][j]});
ans = max(ans , a[i][j] + i - j + mx[i][j]);
}
}
Reset();
for(int i = n;i >= 1;i --){
for(int j = m;j >= 1;j --){
mx[i][j] = max({mx[i + 1][j] , mx[i][j + 1] , -i - j - a[i][j]});
ans = max(ans , a[i][j] + i + j + mx[i][j]);
}
}
cout << max(0LL , ans - 1) << endl;
}
Compilation message (stderr)
maxcomp.cpp:4:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
4 | main(){
| ^~~~
# | 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... |