제출 #197327

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
197327		combi1k1	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1573 ms	47608 KiB

joioi

#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 2005;

typedef pair<int,int>   ii;

int a[N][N];
int f[N][N];
int s[N][N];

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

    int n;  cin >> n;
    int m;  cin >> m;

    int mx = 1, my = 1;
    int Mx = 1, My = 1;

    for(int i = 1 ; i <= n ; ++i)
    for(int j = 1 ; j <= m ; ++j)   {
        cin >> a[i][j];

        if (a[mx][my] > a[i][j])    mx = i, my = j;
        if (a[Mx][My] < a[i][j])    Mx = i, My = j;
    }

    auto check = [&](int lx,int rx,int ly,int ry,int dx,int dy) {
        for(int i = lx ; i != rx ; i += dx)
        for(int j = ly ; j != ry ; j += dy) {
            int area = f[i][j] % 2;

            area += s[i][j - dy];
            area += s[i - dx][j];
            area -= s[i - dx][j - dy];

            if (area == (abs(i - lx) + 1) * (abs(j - ly) + 1))
                s[i][j] = area;
            else    {
                s[i][j] = area - 1;
                if (f[i][j] & 2)    continue;
                else                return  0;
            }
        }
        return  1;
    };

    int L = 0;
    int R = a[Mx][My] - a[mx][my];

    while(L < R)   {
        int M = (L + R) / 2;

        for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)   {
            f[i][j] = 0;

            if (a[i][j] - a[mx][my] <= M)   f[i][j] ^= 1;
            if (a[Mx][My] - a[i][j] <= M)   f[i][j] ^= 2;

            if (f[i][j] == 0)
                goto out;
        }

        if (check(1,n + 1,1,m + 1,1,1)) {
            R = M;
            continue;
        }
        if (check(n,0,1,m + 1,-1,1))    {
            R = M;
            continue;
        }
        if (check(1,n + 1,m,0,1,-1))    {
            R = M;
            continue;
        }
        if (check(n,0,m,0,-1,-1))   {
            R = M;
            continue;
        }
        out:;

        L = M + 1;
    }

    cout << L << endl;
}

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