Submission #1272893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272893		DeathIsAwe	The Kingdom of JOIOI (JOI17_joioi)	C++20	0 / 100	69 ms	31972 KiB

joioi

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define ll long long
#define int long long
int grid[2000][2000], h, w, maxnum = 0, minnum = INT_MAX;
bool visited[2000][2000];


void rotate() {
    vector<vector<int>> copygrid(2000, vector<int>(2000));
    for (int i=0;i<h;i++) {
        for (int j=0;j<w;j++) {
            copygrid[i][j] = grid[w - j - 1][i];
        }
    }
    swap(h, w);
    for (int i=0;i<h;i++) {
        for (int j=0;j<w;j++) {
            grid[i][j] = copygrid[i][j];
        }
    }
}


bool anscheck(int a) {
    if (maxnum - minnum <= a) return true;
    for (int _=0;_<4;_++) {
        bool ans = true;
        for (int i=0;i<h;i++) {
            for (int j=0;j<w;j++) {
                visited[i][j] = false;
            }
        }
        int maxcol = w;
        for (int i=0;i<h;i++) {
            for (int j=0;j<maxcol;j++) {
                if (maxnum - grid[i][j] > a) {
                    maxcol = j;
                } else visited[i][j] = true;
            }
        }
        for (int i=0;i<h;i++) {
            for (int j=0;j<w;j++) {
                if (!visited[i][j] && grid[i][j] - minnum > a) {
                    ans = false; break;
                }
            }
        }
        if (ans) return true;
        ans = true;
        for (int i=0;i<h;i++) {
            for (int j=0;j<w;j++) {
                visited[i][j] = false;
            }
        }
        int mincol = -1;
        for (int i=0;i<h;i++) {
            for (int j=w-1;j>mincol;j--) {
                if (maxnum - grid[i][j] > a) {
                    mincol = j;
                } else visited[i][j] = true;
            }
        }
        for (int i=0;i<h;i++) {
            for (int j=0;j<w;j++) {
                if (!visited[i][j] && grid[i][j] - minnum > a) {
                    ans = false; break;
                }
            }
        }
        if (ans) return true;
        rotate();
    }
    return false;
}


int32_t main() {
    cin >> h >> w;
    for (int i=0;i<h;i++) {
        for (int j=0;j<w;j++) {
            cin >> grid[i][j];
            maxnum = max(maxnum, grid[i][j]);
            minnum = min(minnum, grid[i][j]);
        }
    }


    int top = 1000000000, bottom = 0, mid;
    while (top > bottom + 1) {
        mid = (top + bottom) / 2;
        if (anscheck(mid)) top = mid;
        else bottom = mid;
    }
    cout << top;
}

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