oj.uz

Submission #93908

# Submission time Handle Problem Language Result Execution time Memory
93908 2019-01-13T07:00:07 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 revLin(int n, int m) {
	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 revCol(int n, int m) {	
	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 = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(grid[i][j]<mx-mid){
                temp = max(temp,j);
            }
        }
        for(int j=1;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=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>grid[i][j];
            mx = max(mx,grid[i][j]);
            mn = min(mn,grid[i][j]);
        }
    }
    ans = mx-mn;
    ans = min(check(),ans);
    revLin(n,m);
    ans = min(check(),ans);
    
    revCol(n,m);
 
    revLin(n,m);
 
    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 -