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 ll long long
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define left (h<<1),l,(l + r)/2
#define right ((h<<1)|1),(l + r)/2 + 1,r
#define int ll
using namespace std;
const int N = 1e3 + 3,inf = 1e18;
int a[N][N],n,m,dp[N][N];
void go(){
for (int i = 0; i <= n + 1; i++)
for (int j = 0; j <= m + 1; j++){
if (!i || i > n || !j || j > m) a[i][j] = inf;
dp[i][j] = inf;
}
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
int ans=0;
cin>>n>>m;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cin >> a[i][j];
}
}
go();
for (int i = 1; i <= n; i++){
for (int j = m; j >= 1; j--){
dp[i][j] = min({dp[i][j],a[i - 1][j] + 2,a[i][j + 1] + 2});
dp[i][j] = min({dp[i][j],dp[i - 1][j] + 1,dp[i][j + 1] + 1});
ans=max(ans,a[i][j] - dp[i][j]);
}
}
go();
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
dp[i][j] = min({dp[i][j],a[i - 1][j] + 2,a[i][j - 1] + 2});
dp[i][j] = min({dp[i][j],dp[i - 1][j] + 1,dp[i][j - 1] + 1});
ans=max(ans,a[i][j] - dp[i][j]);
}
}
go();
for (int i = n; i >= 1; i--){
for (int j = 1; j <= m; j++){
dp[i][j] = min({dp[i][j],a[i + 1][j] + 2,a[i][j - 1] + 2});
dp[i][j] = min({dp[i][j],dp[i + 1][j] + 1,dp[i][j - 1] + 1});
ans=max(ans,a[i][j] - dp[i][j]);
}
}
go();
for (int i = n; i >= 1; i--){
for (int j = m; j >= 1; j--){
dp[i][j] = min({dp[i][j],a[i + 1][j] + 2,a[i][j + 1] + 2});
dp[i][j] = min({dp[i][j],dp[i + 1][j] + 1,dp[i][j + 1] + 1});
ans=max(ans,a[i][j] - dp[i][j]);
}
}
cout<<ans;
}
# | 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... |