## Submission #387247

# Submission time Handle Problem Language Result Execution time Memory
387247 2021-04-08T07:31:18 Z Trunkty The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
1 ms 364 KB
```#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int h,w,maxi;
int grid[2005][2005];
int hasmax[2005][3];

bool check(int a){
bool yes=true;
int minl=w,maxo=0,mino=1e9;
for(int i=1;i<=h;i++){
for(int j=1;j<=minl;j++){
if(maxi-grid[i][j]>a){
minl = j-1;
break;
}
}
for(int j=minl;j<=w;j++){
mino = min(mino,grid[i][j]);
maxo = max(maxo,grid[i][j]);
}
if(minl<hasmax[i][2] or maxo-mino>a){
yes = false;
break;
}
}
if(yes){
return true;
}
yes=true;
minl=w,maxo=0,mino=1e9;
for(int i=h;i>=1;i--){
for(int j=1;j<=minl;j++){
if(maxi-grid[i][j]>a){
minl = j-1;
break;
}
}
for(int j=minl;j<=w;j++){
mino = min(mino,grid[i][j]);
maxo = max(maxo,grid[i][j]);
}
if(minl<hasmax[i][2] or maxo-mino>a){
yes = false;
break;
}
}
if(yes){
return true;
}
yes=true;
minl=1,maxo=0,mino=1e9;
for(int i=1;i<=h;i++){
for(int j=w;j>=minl;j--){
if(maxi-grid[i][j]>a){
minl = j+1;
break;
}
}
for(int j=1;j<minl;j++){
mino = min(mino,grid[i][j]);
maxo = max(maxo,grid[i][j]);
}
if(minl>hasmax[i][1] or maxo-mino>a){
yes = false;
break;
}
}
if(yes){
return true;
}
yes=true;
minl=1,maxo=0,mino=1e9;
for(int i=h;i>=1;i--){
for(int j=w;j>=minl;j--){
if(maxi-grid[i][j]>a){
minl = j+1;
break;
}
}
for(int j=1;j<minl;j++){
mino = min(mino,grid[i][j]);
maxo = max(maxo,grid[i][j]);
}
if(minl>hasmax[i][1] or maxo-mino>a){
yes = false;
break;
}
}
if(yes){
return true;
}
return false;
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> h >> w;
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
cin >> grid[i][j];
maxi = max(maxi,grid[i][j]);
}
}
for(int i=1;i<=h;i++){
hasmax[i][1] = 1e9;
for(int j=1;j<=w;j++){
if(grid[i][j]==maxi){
hasmax[i][1] = min(hasmax[i][1],j);
hasmax[i][2] = j;
}
}
}
int low=0,high=maxi-1,mid;
while(low!=high){
mid = (low+high-(low+high)%2)/2;
if(check(mid)){
high = mid;
}
else{
low = mid+1;
}
}

cout << low;

return 0;
}```

#### Subtask #1 0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

#### Subtask #2 0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

#### Subtask #3 0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -