#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
const int SMX = 2e3+3;
int a[SMX][SMX];
int col[SMX][SMX];
bool check(int red, int n, int m)
{
int l[n];
int r[n];
for(int i = 0; i < n; i++)
{
for(r[i] = 0; r[i] < m; r[i]++)
{
if(col[i][r[i]] == red)
break;
}
for(int j = r[i]; j < m; j++)
{
if(col[i][j] == (3ll^red))
return false;
}
l[i] = r[i];
while((l[i] >= 0) && (col[i][l[i]] == 0))
l[i]--;
}
int p = l[0];
bool chad1 = false;
for(int i = 1; i < n && !chad1; i++)
{
if(p > r[i])
{
chad1 = true;
break;
}
p = max(p, l[i]);
}
int q = r[0];
bool chad2 = false;
for(int i = 1; i < n && !chad2; i++)
{
if(q < l[i])
{
chad2 = true;
break;
}
q = min(q, r[i]);
}
if(chad1 && chad2)
return false;
return true;
}
signed main()
{
fast();
int n, m;
cin >> n >> m;
int mx, mn;
mx = -INF; mn = INF;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
cin >> a[i][j];
mx = max(mx, a[i][j]); mn = min(mn, a[i][j]);
}
}
int l = 0;
int r = mx-mn;
while(l < r)
{
int mid = (l+r)/2;
bool fl = true;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
col[i][j] = 0;
if((mx-a[i][j]) > mid)
col[i][j]+=1;
if((a[i][j]-mn) > mid)
col[i][j]+=2;
if(col[i][j] == 3)
fl = false;
}
}
if(!fl)
{
l = mid+1;
continue;
}
//can we seperate colors 1 and 2?
bool works = check(1, n, m)||check(2, n, m);
if(works)
r = mid;
else
l = mid+1;
}
cout << l << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
