oj.uz

Submission #978195

# Submission time Handle Problem Language Result Execution time Memory
978195 2024-05-09T02:41:33 Z 12345678 The Kingdom of JOIOI (JOI17_joioi) C++17
100 / 100
 362 ms 117692 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=2e3+5;

int h, w, mp[nx][nx], l, r, dplmx[nx][nx], dprmx[nx][nx], dplmn[nx][nx], dprmn[nx][nx], mn=INT_MAX;

bool solve1(int x)
{
    int pts=w, cmn=INT_MAX, cmx=0;
    for (int i=1; i<=h; i++)
    {
        while (dplmx[i][pts]>mn+x) pts--;
        cmn=min(cmn, dprmn[i][pts+1]);
        cmx=max(cmx, dprmx[i][pts+1]);
    }
    return (cmx-cmn)<=x;
}

bool solve2(int x)
{
    int pts=w, cmn=INT_MAX, cmx=0;
    for (int i=h; i>=1; i--)
    {
        while (dplmx[i][pts]>mn+x) pts--;
        cmn=min(cmn, dprmn[i][pts+1]);
        cmx=max(cmx, dprmx[i][pts+1]);
    }
    return (cmx-cmn)<=x;
}

bool solve3(int x)
{
    int pts=1, cmn=INT_MAX, cmx=0;
    for (int i=1; i<=h; i++)
    {
        while (dprmx[i][pts]>mn+x) pts++;
        cmn=min(cmn, dplmn[i][pts-1]);
        cmx=max(cmx, dplmx[i][pts-1]);
    }
    return (cmx-cmn)<=x;
}

bool solve4(int x)
{
    int pts=1, cmn=INT_MAX, cmx=0;
    for (int i=h; i>=1; i--)
    {
        while (dprmx[i][pts]>mn+x) pts++;
        cmn=min(cmn, dplmn[i][pts-1]);
        cmx=max(cmx, dplmx[i][pts-1]);
    }
    return (cmx-cmn)<=x;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>h>>w;
    for (int i=1; i<=h; i++) for (int j=1; j<=w; j++) cin>>mp[i][j], mn=min(mn, mp[i][j]);
    for (int i=1; i<=h; i++) dplmn[i][0]=dprmn[i][w+1]=INT_MAX;
    for (int i=1; i<=h; i++) for (int j=1; j<=w; j++) dplmx[i][j]=max(dplmx[i][j-1], mp[i][j]), dplmn[i][j]=min(dplmn[i][j-1], mp[i][j]);
    for (int i=1; i<=h; i++) for (int j=w; j>=1; j--) dprmx[i][j]=max(dprmx[i][j+1], mp[i][j]), dprmn[i][j]=min(dprmn[i][j+1], mp[i][j]);
    l=0, r=1e9;
    while (l<r)
    {
        int md=(l+r)/2;
        if (solve1(md)||solve2(md)||solve3(md)||solve4(md)) r=md;
        else l=md+1;
    }
    cout<<l;
}

/*
3 3
1 1 1
10 10 10
1 1
*/

Subtask #1
15.0 / 15.0

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

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 4 ms 5212 KB Output is correct
17 Correct 5 ms 5464 KB Output is correct
18 Correct 5 ms 5468 KB Output is correct
19 Correct 5 ms 5464 KB Output is correct
20 Correct 4 ms 4956 KB Output is correct
21 Correct 6 ms 5468 KB Output is correct
22 Correct 5 ms 5468 KB Output is correct
23 Correct 6 ms 5464 KB Output is correct
24 Correct 5 ms 4956 KB Output is correct
25 Correct 6 ms 5468 KB Output is correct
26 Correct 5 ms 5468 KB Output is correct
27 Correct 6 ms 5468 KB Output is correct
28 Correct 5 ms 5464 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 0 ms 604 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 4 ms 5212 KB Output is correct
17 Correct 5 ms 5464 KB Output is correct
18 Correct 5 ms 5468 KB Output is correct
19 Correct 5 ms 5464 KB Output is correct
20 Correct 4 ms 4956 KB Output is correct
21 Correct 6 ms 5468 KB Output is correct
22 Correct 5 ms 5468 KB Output is correct
23 Correct 6 ms 5464 KB Output is correct
24 Correct 5 ms 4956 KB Output is correct
25 Correct 6 ms 5468 KB Output is correct
26 Correct 5 ms 5468 KB Output is correct
27 Correct 6 ms 5468 KB Output is correct
28 Correct 5 ms 5464 KB Output is correct
29 Correct 274 ms 97068 KB Output is correct
30 Correct 274 ms 100320 KB Output is correct
31 Correct 285 ms 101864 KB Output is correct
32 Correct 293 ms 101824 KB Output is correct
33 Correct 247 ms 89148 KB Output is correct
34 Correct 286 ms 102328 KB Output is correct
35 Correct 356 ms 117692 KB Output is correct
36 Correct 362 ms 111968 KB Output is correct
37 Correct 360 ms 117612 KB Output is correct