Submission #93903

#	Time	Username	Problem	Language	Result	Execution time	Memory
93903		brcode	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	2 ms	376 KiB

joioi

#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 = 0; i < n / 2; i++) { 
        for (int j = i; j < n - i - 1; j++) { 
  
            int temp = grid[i][j]; 
            grid[i][j] = grid[n - 1 - j][i]; 
            grid[n - 1 - j][i] = grid[n - 1 - i][n - 1 - j]; 
            grid[n - 1 - i][n - 1 - j] = grid[j][n - 1 - i]; 
            grid[j][n - 1 - i] = temp; 
        } 
    } 
} 
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);
    rotate90Clockwise();
    ans = min(check(),ans);
    rotate90Clockwise();
    ans = min(check(),ans);
    rotate90Clockwise();
    cout<<ans<<endl;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40