oj.uz

Submission #197326

# Submission time Handle Problem Language Result Execution time Memory
197326 2020-01-20T11:07:12 Z combi1k1 The Kingdom of JOIOI (JOI17_joioi) C++14
60 / 100
 4000 ms 65632 KB 
#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 = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            s[i][j] = 0,
            h[i][j] = 0;

        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,
                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;

        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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 484 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 6 ms 504 KB Output is correct
14 Correct 3 ms 504 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 484 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 6 ms 504 KB Output is correct
14 Correct 3 ms 504 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 11 ms 4216 KB Output is correct
17 Correct 29 ms 4472 KB Output is correct
18 Correct 11 ms 4472 KB Output is correct
19 Correct 32 ms 4472 KB Output is correct
20 Correct 29 ms 3960 KB Output is correct
21 Correct 41 ms 4600 KB Output is correct
22 Correct 23 ms 4472 KB Output is correct
23 Correct 42 ms 4508 KB Output is correct
24 Correct 13 ms 4088 KB Output is correct
25 Correct 45 ms 4592 KB Output is correct
26 Correct 37 ms 4600 KB Output is correct
27 Correct 38 ms 4492 KB Output is correct
28 Correct 40 ms 4612 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 484 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 6 ms 504 KB Output is correct
14 Correct 3 ms 504 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 11 ms 4216 KB Output is correct
17 Correct 29 ms 4472 KB Output is correct
18 Correct 11 ms 4472 KB Output is correct
19 Correct 32 ms 4472 KB Output is correct
20 Correct 29 ms 3960 KB Output is correct
21 Correct 41 ms 4600 KB Output is correct
22 Correct 23 ms 4472 KB Output is correct
23 Correct 42 ms 4508 KB Output is correct
24 Correct 13 ms 4088 KB Output is correct
25 Correct 45 ms 4592 KB Output is correct
26 Correct 37 ms 4600 KB Output is correct
27 Correct 38 ms 4492 KB Output is correct
28 Correct 40 ms 4612 KB Output is correct
29 Correct 1687 ms 61432 KB Output is correct
30 Correct 2201 ms 64608 KB Output is correct
31 Correct 2146 ms 64504 KB Output is correct
32 Correct 2212 ms 64564 KB Output is correct
33 Correct 570 ms 56696 KB Output is correct
34 Correct 2371 ms 64700 KB Output is correct
35 Correct 3258 ms 65632 KB Output is correct
36 Correct 1812 ms 63564 KB Output is correct
37 Execution timed out 4048 ms 64088 KB Time limit exceeded