oj.uz

Submission #255240

# Submission time Handle Problem Language Result Execution time Memory
255240 2020-07-31T15:54:33 Z test2 The Kingdom of JOIOI (JOI17_joioi) C++14
100 / 100
 1303 ms 86336 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2002;

int n, m;
int a[N][N];
int ans;
int mn = 1e9 + 7, mx;

int ok1[N][N], ok2[N][N];

int mnA[N], mxA[N];
int mnB[N], mxB[N];

bool check(int val)
{
        memset(ok1, 0, sizeof ok1);
        memset(ok2, 0, sizeof ok2);
        for (int i = 0; i < m; i++)
        {
                mnA[i] = n;
                mnB[i] = n;
                mxA[i] = -1;
                mxB[i] = -1;
        }
        
        for (int i = 0; i < n; i++)
        {
                for (int j = 0; j < m; j++)
                {
                        if (a[i][j] - mn <= val)
                                ok1[i][j] = 1;
                        else
                                ok1[i][j] = 0;

                        if (mx - a[i][j] <= val)
                                ok2[i][j] = 1;
                        else
                                ok2[i][j] = 0;

                        if (!ok1[i][j] && !ok2[i][j])
                                return 0;

                        if (ok1[i][j] && !ok2[i][j])
                        {
                                mnA[j] = min(mnA[j], i);
                                mxA[j] = max(mxA[j], i);
                        }
                        if (!ok1[i][j] && ok2[i][j])
                        {
                                mnB[j] = min(mnB[j], i);
                                mxB[j] = max(mxB[j], i);
                        }
                }
        }


        //increasing starting from row 0
        bool k1 = 1, k2 = 1;
        int mnca = -1, mncb = -1;
        for (int i = 0; i < m; i++)
        {
                mnca = max(mnca, mxA[i]);
                mncb = max(mncb, mxB[i]);

                if (mnca >= mnB[i])
                        k1 = 0;
                if (mncb >= mnA[i])
                        k2 = 0;
        }

        if (k1 || k2)
                return 1;

        for (int i = 0; i < n; i++)
        {
                for (int j = 0; j < m; j++)
                {
                        //   int an = ok1[i][j] + ok2[i][j];
                        // cout << an << " ";
                }
                //  cout << "\n";
        }

        //decreasing starting from row 0
        k1 = 1, k2 = 1;
        mnca = -1, mncb = -1;

        for (int i = m - 1; i >= 0; i--)
        {
                mnca = max(mnca, mxA[i]);
                mncb = max(mncb, mxB[i]);

                if (mnca >= mnB[i])
                        k1 = 0;
                if (mncb >= mnA[i])
                        k2 = 0;
        }

        if (k1 || k2)
                return 1;

        // increasing starting at row n

        k1 = 1, k2 = 1;
        int mxca = n, mxcb = n;

        for (int i = 0; i < m; i++)
        {
                mnca = min(mnca, mnA[i]);
                mncb = min(mncb, mnB[i]);

                if (mxca >= mxB[i])
                        k1 = 0;
                if (mxcb >= mxA[i])
                        k2 = 0;
        }
        if (k1 || k2)
                return 1;

        //decreasing starting at row n

        k1 = 1, k2 = 1;
        mxca = n, mxcb = n;

        for (int i = m - 1; i >= 0; i--)
        {
                mnca = min(mnca, mnA[i]);
                mncb = min(mncb, mnB[i]);

                if (mxca >= mxB[i])
                        k1 = 0;
                if (mxcb >= mxA[i])
                        k2 = 0;
        }
        if (k1 | k2)
                return 1;

        return (k1 | k2);
}

int main()
{

        ios_base::sync_with_stdio(0);
        cin.tie(0);
        //freopen("in.in", "r", stdin);

        cin >> n >> m;
        for (int i = 0; i < n; i++)
        {
                for (int j = 0; j < m; j++)
                {
                        cin >> a[i][j];
                        mn = min(mn, a[i][j]);
                        mx = max(mx, a[i][j]);
                }
        }

        int lo = 0, hi = mx - mn;

        for (; lo <= hi;)
        {
                int mid = (lo + hi) >> 1;

                if (check(mid))
                        ans = mid, hi = mid - 1;
                else
                        lo = mid + 1;
        }

        cout << ans;

        return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31736 KB Output is correct
2 Correct 25 ms 31744 KB Output is correct
3 Correct 124 ms 31744 KB Output is correct
4 Correct 130 ms 31744 KB Output is correct
5 Correct 123 ms 31744 KB Output is correct
6 Correct 128 ms 31864 KB Output is correct
7 Correct 126 ms 31928 KB Output is correct
8 Correct 131 ms 31744 KB Output is correct
9 Correct 134 ms 31744 KB Output is correct
10 Correct 133 ms 31744 KB Output is correct
11 Correct 129 ms 31744 KB Output is correct
12 Correct 132 ms 31824 KB Output is correct
13 Correct 137 ms 31744 KB Output is correct
14 Correct 131 ms 31864 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31736 KB Output is correct
2 Correct 25 ms 31744 KB Output is correct
3 Correct 124 ms 31744 KB Output is correct
4 Correct 130 ms 31744 KB Output is correct
5 Correct 123 ms 31744 KB Output is correct
6 Correct 128 ms 31864 KB Output is correct
7 Correct 126 ms 31928 KB Output is correct
8 Correct 131 ms 31744 KB Output is correct
9 Correct 134 ms 31744 KB Output is correct
10 Correct 133 ms 31744 KB Output is correct
11 Correct 129 ms 31744 KB Output is correct
12 Correct 132 ms 31824 KB Output is correct
13 Correct 137 ms 31744 KB Output is correct
14 Correct 131 ms 31864 KB Output is correct
15 Correct 27 ms 31744 KB Output is correct
16 Correct 36 ms 32768 KB Output is correct
17 Correct 96 ms 32896 KB Output is correct
18 Correct 108 ms 32888 KB Output is correct
19 Correct 109 ms 33024 KB Output is correct
20 Correct 105 ms 32760 KB Output is correct
21 Correct 137 ms 33024 KB Output is correct
22 Correct 154 ms 33016 KB Output is correct
23 Correct 147 ms 33024 KB Output is correct
24 Correct 141 ms 32888 KB Output is correct
25 Correct 149 ms 33128 KB Output is correct
26 Correct 154 ms 33024 KB Output is correct
27 Correct 145 ms 33016 KB Output is correct
28 Correct 138 ms 33024 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31736 KB Output is correct
2 Correct 25 ms 31744 KB Output is correct
3 Correct 124 ms 31744 KB Output is correct
4 Correct 130 ms 31744 KB Output is correct
5 Correct 123 ms 31744 KB Output is correct
6 Correct 128 ms 31864 KB Output is correct
7 Correct 126 ms 31928 KB Output is correct
8 Correct 131 ms 31744 KB Output is correct
9 Correct 134 ms 31744 KB Output is correct
10 Correct 133 ms 31744 KB Output is correct
11 Correct 129 ms 31744 KB Output is correct
12 Correct 132 ms 31824 KB Output is correct
13 Correct 137 ms 31744 KB Output is correct
14 Correct 131 ms 31864 KB Output is correct
15 Correct 27 ms 31744 KB Output is correct
16 Correct 36 ms 32768 KB Output is correct
17 Correct 96 ms 32896 KB Output is correct
18 Correct 108 ms 32888 KB Output is correct
19 Correct 109 ms 33024 KB Output is correct
20 Correct 105 ms 32760 KB Output is correct
21 Correct 137 ms 33024 KB Output is correct
22 Correct 154 ms 33016 KB Output is correct
23 Correct 147 ms 33024 KB Output is correct
24 Correct 141 ms 32888 KB Output is correct
25 Correct 149 ms 33128 KB Output is correct
26 Correct 154 ms 33024 KB Output is correct
27 Correct 145 ms 33016 KB Output is correct
28 Correct 138 ms 33024 KB Output is correct
29 Correct 762 ms 68796 KB Output is correct
30 Correct 780 ms 69164 KB Output is correct
31 Correct 947 ms 58360 KB Output is correct
32 Correct 684 ms 59000 KB Output is correct
33 Correct 506 ms 65552 KB Output is correct
34 Correct 853 ms 56776 KB Output is correct
35 Correct 990 ms 58616 KB Output is correct
36 Correct 805 ms 81100 KB Output is correct
37 Correct 1303 ms 86336 KB Output is correct