제출 #1315088

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1315088		amloxg	The Kingdom of JOIOI (JOI17_joioi)	C++20	0 / 100	1 ms	332 KiB

joioi

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;

const int MAX_BOARD_LENGTH = 2000;
const int MAX_VAL = 1e9;

int height, width;
int max_val=-1, min_val=MAX_VAL+7;
int board[MAX_BOARD_LENGTH+7][MAX_BOARD_LENGTH+7];
int tmp[MAX_BOARD_LENGTH+7][MAX_BOARD_LENGTH+7];

void boardRotate90(){
    for (int i = 1; i <= height; ++i)
        for (int j = 1; j <= width; ++j)
            tmp[width-j+1][i] = board[i][j];

    swap(height, width);
    for (int i = 1; i <= height; ++i)
        for (int j = 1; j <= width; ++j)
            board[i][j] = tmp[i][j];
}

void boardFlipHorizontal(){
    for (int i = 1; i <= height; ++i)
        for (int j = 1; j <= width; ++j)
            tmp[i][width-j+1] = board[i][j];

    for (int i = 1; i <= height; ++i)
        for (int j = 1; j <= width; ++j)
            board[i][j] = tmp[i][j];
}

bool isAchievable(int k){
    if (max_val - min_val <= k) return true;
    int curr_max=-1, curr_min=MAX_VAL+7;
    int max_height = 0;
    for (int j = 1; j <= width; ++j){
        int i = height;
        while(i > max_height && board[i][j] <= min_val + k) i--;
        max_height = i;
        while(i > 0){
            curr_max = max(curr_max, board[i][j]);
            curr_min = min(curr_min, board[i][j]);
            --i;
        }
    }
    return (curr_max - curr_min <= k);
}

int getRes(){
    int low=0, high=max_val-min_val;
    while(low < high){
        int mid = (low+high)/2;
        if (isAchievable(mid)) high = mid;
        else low = mid+1;
    }
    return high;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> height >> width;
    for (int i = 1; i <= height; ++i) 
        for (int j = 1; j <= width; ++j){
            cin >> board[i][j];
            max_val = max(max_val, board[i][j]);
            min_val = min(min_val, board[i][j]);
        }
    
    int res = getRes();
    boardRotate90();
    res = min(res, getRes());
    boardFlipHorizontal();
    res = min(res, getRes());
    boardRotate90();
    res = min(res, getRes());
    
    cout << res << '\n';

    return 0;
}

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