제출 #253068

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
253068		Tuk1352	The Kingdom of JOIOI (JOI17_joioi)	C++11	100 / 100	3383 ms	160292 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()
{
    vector <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_back({A[i][y],{i,y}});
            G[i][y] = 1;
            Max = max(A[i][y], Max);
            Min = min(A[i][y], Min);
        }
    }
    sort(Q.begin(),Q.end());
    Re = Max - Min;
    Mi2 = Min;
    for (int u = 0; u < n*m; u++)
    {
        I = Q[u].second.first;
        Y = Q[u].second.second;
        a = Q[u].first;
        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: 40 / 40