Submission #894033

#	Time	Username	Problem	Language	Result	Execution time	Memory
894033		raphaelp	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1403 ms	149328 KiB

joioi

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N, M;
    cin >> N >> M;
    int high = 0, low = 1000000000;
    vector<vector<int>> Tab(N, vector<int>(M));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> Tab[i][j];
            high = max(high, Tab[i][j]);
            low = min(low, Tab[i][j]);
        }
    }
    vector<vector<int>> colmin(N, vector<int>(M)), colmax(N, vector<int>(M)), rowminlr(N, vector<int>(M)), rowminrl(N, vector<int>(M)), rowmaxlr(N, vector<int>(M)), rowmaxrl(N, vector<int>(M));
    for (int i = 0; i < M; i++)
    {
        colmin[N - 1][i] = Tab[N - 1][i];
        colmax[N - 1][i] = Tab[N - 1][i];
    }
    for (int i = N - 2; i >= 0; i--)
    {
        for (int j = 0; j < M; j++)
        {
            colmin[i][j] = min(colmin[i + 1][j], Tab[i][j]);
            colmax[i][j] = max(colmax[i + 1][j], Tab[i][j]);
        }
    }
    for (int i = 0; i < N; i++)
    {
        rowminlr[i][0] = Tab[i][0];
        rowmaxlr[i][0] = Tab[i][0];
        rowminrl[i][M - 1] = Tab[i][M - 1];
        rowmaxrl[i][M - 1] = Tab[i][M - 1];
    }
    for (int j = 1; j < M; j++)
    {
        for (int i = 0; i < N; i++)
        {
            rowminlr[i][j] = min(rowminlr[i][j - 1], Tab[i][j]);
            rowmaxlr[i][j] = max(rowmaxlr[i][j - 1], Tab[i][j]);
        }
    }
    for (int j = M - 2; j >= 0; j--)
    {
        for (int i = 0; i < N; i++)
        {
            rowminrl[i][j] = min(rowminrl[i][j + 1], Tab[i][j]);
            rowmaxrl[i][j] = max(rowmaxrl[i][j + 1], Tab[i][j]);
        }
    }
    int best = 1234567890;
    int maxx = 0, minn = 1000000000;
    int x = 0, y = M - 1;
    while (x < N && y >= 0)
    {
        int a = min(minn, rowminlr[x][y]);
        int b = max(maxx, colmax[x][y]);
        if (high - a > b - low)
        {
            maxx = b;
            y--;
        }
        else
        {
            minn = a;
            x++;
        }
    }
    best = min(best, max(high - minn, maxx - low));
    maxx = 0, minn = 1000000000;
    x = 0, y = M - 1;
    while (x < N && y >= 0)
    {
        int a = min(minn, colmin[x][y]);
        int b = max(maxx, rowmaxlr[x][y]);
        if (high - a > b - low)
        {
            maxx = b;
            x++;
        }
        else
        {
            minn = a;
            y--;
        }
    }
    best = min(best, max(high - minn, maxx - low));
    maxx = 0, minn = 1000000000;
    x = 0, y = 0;
    while (x < N && y < M)
    {
        int a = min(minn, rowminrl[x][y]);
        int b = max(maxx, colmax[x][y]);
        if (high - a > b - low)
        {
            maxx = b;
            y++;
        }
        else
        {
            minn = a;
            x++;
        }
    }
    best = min(best, max(high - minn, maxx - low));
    maxx = 0, minn = 1000000000;
    x = 0, y = 0;
    while (x < N && y < M)
    {
        int a = min(minn, colmin[x][y]);
        int b = max(maxx, rowmaxrl[x][y]);
        if (high - a > b - low)
        {
            maxx = b;
            x++;
        }
        else
        {
            minn = a;
            y++;
        }
    }
    best = min(best, max(high - minn, maxx - low));
    cout << best;
}

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