#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 2048;
int a[N][N];
int n, m;
int len[N];
bool can_extend(int i, int mx)
{
if (i > 0 && len[i-1] <= len[i])
return 0;
if (len[i] == m || a[i][len[i]] > mx)
return 0;
return 1;
}
int solve()
{
static bool col[N][N];
int mn1v = 2e9, mx1v = -1, mn2 = 0, mx2 = n*m-1;
vector<pair<int,pii>> alts;
memset(len, 0, sizeof(len));
Loop (i,0,n) Loop (j,0,m) {
alts.push_back({a[i][j], {i, j}});
col[i][j] = 1;
}
sort(alts.begin(), alts.end());
int ans = 2e9;
for (auto [mx, pos] : alts) {
int row = pos.first;
Loop (r,row,n) {
if (!can_extend(r, mx))
break;
while (can_extend(r, mx)) {
mx1v = max(mx1v, a[r][len[r]]);
mn1v = min(mn1v, a[r][len[r]]);
col[r][len[r]] = 0;
len[r]++;
}
}
for (; mn2 < n*m && !col[alts[mn2].second.first][alts[mn2].second.second]; ++mn2);
for (; mx2 >= 0 && !col[alts[mx2].second.first][alts[mx2].second.second]; --mx2);
if (mx1v == -1 || mx2 == -1)
continue;
ans = min(ans, max(mx1v - mn1v, alts[mx2].first - alts[mn2].first));
}
return ans;
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n >> m;
Loop (i,0,n) Loop (j,0,m)
cin >> a[i][j];
int ans = 2e9;
ans = min(ans, solve());
Loop (i,0,n/2) Loop (j,0,m)
swap(a[i][j], a[n-1-i][j]);
ans = min(ans, solve());
Loop (i,0,n) Loop (j,0,m/2)
swap(a[i][j], a[i][m-1-j]);
ans = min(ans, solve());
Loop (i,0,n/2) Loop (j,0,m)
swap(a[i][j], a[n-1-i][j]);
ans = min(ans, solve());
cout << ans << '\n';
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
0 ms |
340 KB |
Output is correct |
| 15 |
Correct |
2 ms |
468 KB |
Output is correct |
| 16 |
Correct |
25 ms |
2768 KB |
Output is correct |
| 17 |
Correct |
23 ms |
2804 KB |
Output is correct |
| 18 |
Correct |
23 ms |
2752 KB |
Output is correct |
| 19 |
Correct |
21 ms |
2788 KB |
Output is correct |
| 20 |
Correct |
20 ms |
2600 KB |
Output is correct |
| 21 |
Correct |
23 ms |
2740 KB |
Output is correct |
| 22 |
Correct |
23 ms |
2788 KB |
Output is correct |
| 23 |
Correct |
26 ms |
2760 KB |
Output is correct |
| 24 |
Correct |
21 ms |
2604 KB |
Output is correct |
| 25 |
Correct |
22 ms |
2756 KB |
Output is correct |
| 26 |
Correct |
23 ms |
2808 KB |
Output is correct |
| 27 |
Correct |
22 ms |
2804 KB |
Output is correct |
| 28 |
Correct |
23 ms |
2716 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
340 KB |
Output is correct |
| 14 |
Correct |
0 ms |
340 KB |
Output is correct |
| 15 |
Correct |
2 ms |
468 KB |
Output is correct |
| 16 |
Correct |
25 ms |
2768 KB |
Output is correct |
| 17 |
Correct |
23 ms |
2804 KB |
Output is correct |
| 18 |
Correct |
23 ms |
2752 KB |
Output is correct |
| 19 |
Correct |
21 ms |
2788 KB |
Output is correct |
| 20 |
Correct |
20 ms |
2600 KB |
Output is correct |
| 21 |
Correct |
23 ms |
2740 KB |
Output is correct |
| 22 |
Correct |
23 ms |
2788 KB |
Output is correct |
| 23 |
Correct |
26 ms |
2760 KB |
Output is correct |
| 24 |
Correct |
21 ms |
2604 KB |
Output is correct |
| 25 |
Correct |
22 ms |
2756 KB |
Output is correct |
| 26 |
Correct |
23 ms |
2808 KB |
Output is correct |
| 27 |
Correct |
22 ms |
2804 KB |
Output is correct |
| 28 |
Correct |
23 ms |
2716 KB |
Output is correct |
| 29 |
Correct |
2801 ms |
93244 KB |
Output is correct |
| 30 |
Correct |
2738 ms |
99944 KB |
Output is correct |
| 31 |
Correct |
2947 ms |
117264 KB |
Output is correct |
| 32 |
Correct |
2947 ms |
110056 KB |
Output is correct |
| 33 |
Correct |
2517 ms |
92180 KB |
Output is correct |
| 34 |
Correct |
2927 ms |
117408 KB |
Output is correct |
| 35 |
Correct |
2730 ms |
128472 KB |
Output is correct |
| 36 |
Correct |
2283 ms |
95332 KB |
Output is correct |
| 37 |
Correct |
2710 ms |
95920 KB |
Output is correct |
