Submission #253065

#	Time	Username	Problem	Language	Result	Execution time	Memory
253065		Tuk1352	The Kingdom of JOIOI (JOI17_joioi)	C++11	60 / 100	4077 ms	142860 KiB

joioi

#include <bits/stdc++.h>
using namespace std;

int A[2001][2001], B[2001][2001], n, m;

void Rotate()
{
    for (int i = 0; i < n; i++)
    {
        for (int y = 0; y < m; y++)
        {
            B[m-y-1][i] = A[i][y];
        }
    }
    for (int i = 0; i <= 2000; i++)
    {
        for (int y = 0; y <= 2000; y++)
        {
            A[i][y] = B[i][y];
        }
    }
    swap(n, m);
}

long long Solve()
{
    priority_queue <pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> Q;
    int G[n][m], Max=0, Min=2000000000, Re=2000000000, I, Y, a, Mi2=2000000000, Ma2=0;
    for (int i = 0; i < n; i++)
    {
        for (int y = 0; y < m; y++)
        {
            Q.push({A[i][y],{i,y}});
            G[i][y] = 1;
            Max = max(A[i][y], Max);
            Min = min(A[i][y], Min);
        }
    }
    Re = Max - Min;
    Mi2 = Min;
    while (Q.size() > 0)
    {
        I = Q.top().second.first;
        Y = Q.top().second.second;
        a = Q.top().first;
        Q.pop();
        if (G[I][Y] == 0)
        {
            continue;
        }
        if (Ma2 != 0)
        {
            Re = min(Re, max(Ma2-Mi2, Max-a));
        }
        for (int i = I; i >= 0; i--)
        {
            if (G[i][Y] == 0)
            {
                break;
            }
            for (int y = Y; y >= 0; y--)
            {
                if (G[i][y] == 0)
                {
                    break;
                }
                Ma2 = max(Ma2, A[i][y]);
                G[i][y] = 0;
            }
        }
    }
    return Re;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    long long Mi=2000000000;
    for (int i = 0; i < n; i++)
    {
        for (int y = 0; y < m; y++)
        {
            cin >> A[i][y];
        }
    }
    Mi = min(Mi, Solve());
    Rotate();
    Mi = min(Mi, Solve());
    Rotate();
    Mi = min(Mi, Solve());
    Rotate();
    Mi = min(Mi, Solve());
    cout << Mi;
    return 0;
}

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