Submission #1248726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248726		vicvic	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	698 ms	63232 KiB

joioi

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int NMAX=2000;
int mat[NMAX+5][NMAX+5], n, m, b[NMAX+5][NMAX+5], mx=-1e9, mn=1e9;;
bool check (int val)
{
    int crt=0;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            if (mx-val>mat[i][j])
                crt=max (crt, j);
        }
        for (int j=1;j<=crt;j++)
        {
            if (mn+val<mat[i][j])
                return 0;
        }
    }
    return 1;
}
void rot ()
{
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            b[i][j]=mat[i][j];
        }
    }
    for (int i=1;i<=m;i++)
    {
        for (int j=1;j<=n;j++)
        {
            mat[i][j]=b[j][m-i+1];
        }
    }
    swap (n, m);
}
int32_t main ()
{
    ios_base :: sync_with_stdio (0);
    cin.tie (nullptr);
    cin >> n >> m;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            cin >> mat[i][j];
            mx=max (mx, mat[i][j]);
            mn=min (mn, mat[i][j]);
        }
    }
    int ans=1e18;
    for (int i=1;i<=7;i++, rot ())
    {
        int st=0, dr=mx-mn, poz=-1;
        while (st<=dr)
        {
            int mij = (st+dr) >> 1;
            if (check (mij))
                dr=mij-1, poz=mij;
            else
                st=mij+1;
        }
        if (poz==-1)
            continue;
        ans=min (ans, poz);
    }
    cout << ans;
    return 0;
}

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