Submission #1275240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275240		hoangtien69	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	2429 ms	63220 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e3 + 5;
const int INF = 1e11;

int a[MAXN][MAXN];
int n, m;
int maxx = -1;
int b[MAXN][MAXN];

void xoay()
{
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            b[i][j] = a[n - j + 1][i];
        }
    }
    swap(n, m);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            a[i][j] = b[i][j];
        }
    }
}
bool ck(int mid)
{
    int pos = INF;
    int mx = -INF;
    int mn = INF;
    for (int i = 1; i <= n; i++)
    {
        int cur = 0;
        while(cur < m and a[i][cur + 1] >= maxx - mid) cur++;
        pos = min(pos, cur);
        for (int j = pos + 1; j <= m; j++)
        {
            mx = max(mx, a[i][j]);
            mn = min(mn, a[i][j]);
        }
    }
    return (mx == -INF || mx - mn <= mid);
}
bool peal(int mid)
{
    bool cak1 = ck(mid);
    xoay();
    bool cak2 = ck(mid);
    xoay();
    bool cak3 = ck(mid);
    xoay();
    bool cak4 = ck(mid);
    xoay();
    if (cak1 == true || cak2 == true || cak3 == true || cak4 == true)
    {
        return true;
    }
    return false;
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            maxx = max(maxx, a[i][j]);
        }
    }
    int l = 0;
    int r = 1e9;
    int ans = -1;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        if (peal(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << ans;
}

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