Submission #1269842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269842		DJ035	The Kingdom of JOIOI (JOI17_joioi)	C++20	0 / 100	1 ms	576 KiB

joioi

#include <bits/stdc++.h>
#define sanic ios_base::sync_with_stdio(0)
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using pi = pair<ll, ll>;
const ll MEM = 2002;
const ll MOD = 1000000007;
const ll INF = 9e17;
ll gcd(ll a, ll b)
{
    if (a % b)
        return gcd(b, a % b);
    return b;
}
ll t, n, m, l;
ll a[MEM][MEM];
ll dpu[MEM][MEM], dpd[MEM][MEM], mnu[MEM][MEM], mnd[MEM][MEM], mxu[MEM][MEM], mxd[MEM][MEM];
int main()
{
    sanic;
    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];
    for (int j = 1; j <= m; j++)
    {
        mxu[1][j] = mnu[1][j] = a[1][j];
        mxd[n][j] = mnd[n][j] = a[n][j];
        for (int i = 2; i <= n; i++)
        {
            mxu[i][j] = max(mxu[i - 1][j], a[i][j]);
            mnu[i][j] = min(mnu[i - 1][j], a[i][j]);
        }
        for (int i = n - 1; i > 0; i--)
        {
            mxd[i][j] = max(mxd[i + 1][j], a[i][j]);
            mnd[i][j] = min(mnd[i + 1][j], a[i][j]);
        }
    }
    for (int i = 0; i <= n; i++)
        dpu[i][1] = max(mxu[i][1] - mnu[i][1], mxd[i + 1][1] - mnd[i + 1][1]);

    for (int j = 2; j <= m; j++)
    {
        ll o = INF;
        for (int i = 0; i <= n; i++)
        {
            o = min(dpu[i][j - 1], o);
            dpu[i][j] = max(o, max(mxu[i][j] - mnu[i][j], mxd[i + 1][j] - mnd[i + 1][j]));
        }
    }
    for (int i = n + 1; i > 0; i--)
        dpd[i][1] = max(mxu[i - 1][1] - mnu[i - 1][1], mxd[i][1] - mnd[i][1]);

    for (int j = 2; j <= m; j++)
    {
        ll o = INF;
        for (int i = n + 1; i > 0; i--)
        {
            o = min(dpd[i][j - 1], o);
            dpd[i][j] = max(o, max(mxu[i - 1][j] - mnu[i - 1][j], mxd[i][j] - mnd[i][j]));
        }
    }
    ll ans = INF;
    for (int i = 0; i <= n; i++)
        ans = min(ans, dpu[i][m]);
    for (int i = 1; i <= n + 1; i++)
        ans = min(ans, dpd[i][m]);
    cout << ans << '\n';
}

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