Submission #837255

#	Time	Username	Problem	Language	Result	Execution time	Memory
837255		Liudas	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	1772 ms	16024 KiB

joioi

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> grid;
void reverse_rows(){
    for(auto &i : grid){
        reverse(i.begin(), i.end());
    }
}
void reverse_cols(){
    reverse(grid.begin(), grid.end());
}
int good(int mini, int K){
    int H = grid.size();
    int W = grid[0].size();
    int can_go = W;
    int mind = 1e9, maxd = 0;
    for(int i = 0; i < H; i ++){
        for(int j = 0; j < can_go; j ++){
            if(mini + K < grid[i][j])can_go = j;
        }
        for(int j = can_go; j < W; j ++){
            maxd = max(grid[i][j], maxd);
            mind = min(grid[i][j], mind);
        }
    }
    return maxd-mind;
}
int check(int K, int mini){
    int pass = 0;
    reverse_rows();
    pass |= (good(mini, K) <= K);
    reverse_cols();
    pass |= (good(mini, K) <= K);
    reverse_rows();
    pass |= (good(mini, K) <= K);
    reverse_cols();
    pass |= (good(mini, K) <= K);
    return pass;
}
int main(){
    int H, W;
    cin >> H >> W;
    int mini = 1e9;
    grid.assign(H, vector<int>(W));
    for(int i = 0; i < H; i ++){
        for(int j = 0; j < W; j ++){
            cin >> grid[i][j];
            mini = min(grid[i][j], mini);
        }
    }
    int L = 0, R = 1e9;
    while(L < R){
        int mid = (L + R) / 2;
        int t = check(mid, mini);
        if(t){
            R = mid;
        }
        else{
            L = mid + 1;
        }
    }
    cout << L << endl;
    return 0;
}

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