oj.uz

Submission #592707

# Submission time Handle Problem Language Result Execution time Memory
592707 2022-07-09T13:42:22 Z hail The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 1 ms 324 KB 
#include <bits/stdc++.h>

using namespace std;

int h, w;
int max_alt{0};
int min_alt(1e9);

bool check_kingdom(int x, vector<vector<int>>& country)
{
    int border{w};
    bool valid;
    //min left top
    if(country[0][0]-min_alt<=x)
    {
        valid=true;
        for(int i=0; i<h; i++)
        {
            for(int j=0; j<w; j++)
            {
                if(j<border)
                {
                    if(country[i][j]-min_alt>x) border=j;
                }
                else
                {
                    if(max_alt-country[i][j]>x)
                    {
                        valid=false;
                        break;
                    }
                }
            }
            if(not valid) break;
        }
        if(valid) return true;
    }
    //min left bottom
    border=w;
    if(country[h-1][0]-min_alt<=x)
    {
        valid=true;
        for(int i=h-1; i>=0; i--)
        {
            for(int j=0; j<w; j++)
            {
                if(j<border)
                {
                    if(country[i][j]-min_alt>x) border=j;
                }
                else
                {
                    if(max_alt-country[i][j]>x)
                    {
                        valid=false;
                        break;
                    }
                }
            }
            if(not valid) break;
        }
        if(valid) return true;
    }
    //max left top
    border=w;
    if(max_alt-country[0][0]<=x)
    {
        valid=true;
        for(int i=0; i<h; i++)
        {
            for(int j=0; j<w; j++)
            {
                if(j<border)
                {
                    if(max_alt-country[i][j]>x) border=j;
                }
                else
                {
                    if(country[i][j]-min_alt>x)
                    {
                        valid=false;
                        break;
                    }
                }
            }
            if(not valid) break;
        }
        if(valid) return true;
    }
    //max left bottom
    border=w;
    if(max_alt-country[h-1][0]<=x)
    {
        valid=true;
        for(int i=h-1; i>=0; i--)
        {
            for(int j=0; j<w; j++)
            {
                if(j<border)
                {
                    if(max_alt-country[i][j]>x) border=j;
                }
                else
                {
                    if(country[i][j]-min_alt>x)
                    {
                        valid=false;
                        break;
                    }
                }
            }
            if(not valid) break;
        }
        if(valid) return true;
    }
    return false;
}

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

    cin>>h>>w;
    vector<int> row(w, 0);
    vector<vector<int>> country(h, row);


    for(int i=0; i<h; i++)
    {
        for(int j=0; j<w; j++)
        {
            cin>>country[i][j];
            max_alt=max(max_alt, country[i][j]);
            min_alt=min(min_alt, country[i][j]);
        }
    }

    int high=max_alt-min_alt;
    int low=0;

    int mid;

    while(high-low>1)
    {
        mid=(high+low)/2;
        if(check_kingdom(mid, country)) high=mid;
        else low=mid;
    }

    cout<<high;

    return 0;

}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Halted 0 ms 0 KB -