Submission #1116542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116542		staszic_ojuz	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	1024 ms	55232 KiB

joioi

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> m;
int inf = 2000000000;
int mini = inf;
int h,w;
bool check(int x)
{
    int jl = w;
    int max2 = 0,min2 = inf;
    for(int i = 0; i<h; i++)
    {
        for(int j = 0; j<w; j++)
        {
            if(m[i][j] > x+mini)
            {
                jl = min(j,jl);
            }
            if(j >= jl)
            {
                max2 = max(max2,m[i][j]);
                min2 = min(min2,m[i][j]);
            }
        }
    }
    if(max2 - min2 <= x)
    {
        return true;
    }
    else
    {
        return false;
    }
}
int bs()
{
    int l = -1;
    int r = 1e9;
    while(l+1 < r)
    {
        int mid = (l+r)/2;
        if(check(mid))
        {
            r = mid;
        }
        else
        {
            l = mid;
        }
    }
    return r;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>h>>w;
    m.resize(h);
    for(int i = 0; i<h; i++)
    {
        for(int j = 0; j<w; j++)
        {
            int x;
            cin>>x;
            m[i].push_back(x);
            mini = min(mini,x);
        }
    }
    int ans = bs();
    reverse(m.begin(),m.end());
    ans = min(ans,bs());
    for(int i = 0; i<h; i++)
    {
        reverse(m[i].begin(),m[i].end());
    }
    ans = min(ans,bs());
    reverse(m.begin(),m.end());
    ans = min(ans,bs());
    cout<<ans;
}

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