oj.uz

Submission #93904

# Submission time Handle Problem Language Result Execution time Memory
93904 2019-01-13T06:26:32 Z brcode The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 2 ms 376 KB 
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;
const int MAXN = 2010;
int grid[2010][2010];
int n,m;
int mx;
int ans;
int mn = 1e9;
void rotate90Clockwise(){ 
    for (int i = 1; i <= n / 2; i++) {
		for (int j = 1; j <= m; j++) {
			swap(grid[i][j], grid[n - i + 1][j]); 
		    
		}
	} 
    
}
void rotate90Clockwise2(){ 
    for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m/2; j++) {
			swap(grid[i][j], grid[i][m - j + 1]); 
		    
		}
	} 
    
}

bool find(int mid){
    int temp = -1;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(grid[i][j]<mx-mid){
                temp = max(temp,j);
            }
        }
        for(int j=0;j<=temp;j++){
            if(grid[i][j]>mn+mid){
                return false;
            }
        }
    }
    return true;
}
int check(){
    int l = 0;
    int r = mx-mn;
    int ans = 0;
    while(l<=r){
        int mid = (l+r)/2;
       // cout<<mid<<endl;
        if(find(mid)){
            ans = mid;
            r = mid-1;
        }else{
            l = mid+1;
        }
    }
    return ans;
}
int main() {
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>grid[i][j];
            mx = max(mx,grid[i][j]);
            mn = min(mn,grid[i][j]);
        }
    }
    ans = 1000000000;
    ans = min(check(),ans);
    rotate90Clockwise();
    ans = min(check(),ans);
    rotate90Clockwise2();
    ans = min(check(),ans);
    rotate90Clockwise();
    ans = min(check(),ans);
    rotate90Clockwise2();
    cout<<ans<<endl;
}

Subtask #1
0 / 15.0

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

Subtask #2
0 / 45.0

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

Subtask #3
0 / 40.0

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