Submission #197321

#	Time	Username	Problem	Language	Result	Execution time	Memory
197321		combi1k1	The Kingdom of JOIOI (JOI17_joioi)	C++14	0 / 100	2 ms	504 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 h[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) if (f[i][j] & 1)    {
            int area = 1;

            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,
                h[i][j] = 1;
            else
                s[i][j] = area - 1;
        }
        for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)   if(!h[i][j])    {
            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;

        bool ok = 1;

        for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)   {
            f[i][j] = 0;
            s[i][j] = 0;
            h[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)   {
                ok = 0;
                goto out;
            }
        }

        ok = 0;
        ok |= check(1,n + 1,1,m + 1,1,1);
        ok |= check(n,0,1,m + 1,-1,1);
        ok |= check(1,n + 1,m,0,1,-1);
        ok |= check(n,0,m,0,-1,-1);

        out:;

        if (ok) R = M;
        else    L = M + 1;
    }

    cout << L << endl;
}

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