Submission #1181643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181643		MongHwa	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	345 ms	16160 KiB

joioi

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include <iostream>
using namespace std;

#define INF 0x7f7f7f7f
#define X first
#define Y second

int stage[2005][2005];
int val[2005];
pair<int, int> bound[2005];

bool solve(int H, int W, int aval, int bval, int target)
{
    for(int j = 0; j < W; j++)
    {
        val[j] = H;
        for(int i = H-1; i >= 0; i--)
        {
            if(abs(aval-stage[i][j]) <= target)
                val[j] = i;
            else
                break;
        }
    }

    for(int j = 0; j < W; j++)
    {
        bound[j] = (val[j] == 0 ? make_pair(0, 0) : make_pair(-1, -1));
        for(int i = 0; i < H; i++)
        {
            if(abs(bval-stage[i][j]) <= target)
            {
                if(i >= val[j]-1)
                {
                    if(bound[j].X == -1)
                        bound[j].X = i+1;
                    bound[j].Y = i+1;
                }
            }
            else
                break;
        }

        if(bound[j].X == -1)
            return false;
    }

    bool ret = 1;
    int x = bound[0].Y;
    for(int j = 1; j < W; j++)
    {
        if(x < bound[j].X)
            ret = 0;
        x = min(x, bound[j].Y);
    }

    if(ret)
        return true;
    
    ret = 1;
    x = bound[W-1].Y;
    for(int j = W-2; j >= 0; j--)
    {
        if(x < bound[j].X)
            ret = 0;
        x = min(x, bound[j].Y);
    }

    if(ret)
        return true;
    return false;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int H, W;
    cin >> H >> W;

    int mn = INF, mx = 0;
    for(int i = 0; i < H; i++)
        for(int j = 0; j < W; j++)
        {
            cin >> stage[i][j];
            mn = min(mn, stage[i][j]);
            mx = max(mx, stage[i][j]);
        }
    
    int l = 0, r = mx-mn;
    while(l < r)
    {
        int mid = (l+r) / 2;

        if(solve(H, W, mn, mx, mid) || solve(H, W, mx, mn, mid))
            r = mid;
        else
            l = mid+1;
    }

    cout << l << '\n';
}

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