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>
using namespace std;
//#define FILE_IO
int N, M, ans, cost;
int mn, mx;
int pfxmn[2005], sfxmx[2005];
int aux[2005][2005];
int a[2005][2005];
int dp[2005][2005];
void solve()
{
for(int i = 1; i <= N; i++)
{
pfxmn[0] = 1 << 30;
for(int j = 1; j <= M; j++) pfxmn[j] = min(pfxmn[j - 1], a[i][j]);
sfxmx[M + 1] = -1;
for(int j = M; j >= 1; j--) sfxmx[j] = max(sfxmx[j + 1], a[i][j]);
for(int j = M; j >= 0; j--)
{
cost = max(mx - pfxmn[j], sfxmx[j + 1] - mn);
dp[i][j] = max(dp[i - 1][j], cost);
if(j < M) dp[i][j] = min(dp[i][j], dp[i][j + 1]);
}
}
ans = min(ans, dp[N][0]);
}
void rotate90()
{
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
{
aux[i][j] = a[i][j];
a[i][j] = 0;
}
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
a[j][N - i + 1] = aux[i][j];
swap(N, M);
}
int main()
{
#ifdef FILE_IO
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
scanf("%d%d", &N, &M);
mn = 1 << 30, mx = -1;
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
{
scanf("%d", &a[i][j]);
mn = min(mn, a[i][j]);
mx = max(mx, a[i][j]);
}
ans = mx - mn;
solve();
rotate90();
solve();
rotate90();
solve();
rotate90();
solve();
printf("%d\n", ans);
return 0;
}
Compilation message (stderr)
joioi.cpp: In function 'int main()':
joioi.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~
joioi.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i][j]);
~~~~~^~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |