Submission #1308043

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308043		VMaksimoski008	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	1887 ms	31876 KiB

joioi

#include <bits/stdc++.h>
using namespace std;

int n, m, ans=1e9, a[2001][2001], mn=1e9, mx=0;

void rotate() {
    int b[m+1][n+1];
    for(int i=1; i<=m; i++)
        for(int j=1; j<=n; j++)
            b[m+1-i][j] = a[j][i];
    
    for(int i=1; i<=m; i++)
        for(int j=1; j<=n; j++) 
            a[i][j] = b[i][j];
    swap(n, m);
}

void baba() {
    rotate();
    
    int l=0, r=1e9, res=1e9;
    while(l <= r) {
        int mid = (l + r) / 2;
        int ok = 1;

        int R = 1e9;
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++)
                if(a[i][j] > mn + mid) R = min(R, j);
            for(int j=R; j<=m; j++)
                if(a[i][j] < mx - mid) ok = 0;
        }

        if(ok) res = mid, r = mid - 1;
        else l = mid + 1;
    }
    ans = min(ans, res);   
}

signed main() {
    cin >> n >> m;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin >> a[i][j];
            mn = min(mn, a[i][j]);
            mx = max(mx, a[i][j]);
        }
    }

    for(int i=0; i<4; i++)
        baba();
    cout << ans << '\n';
}

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