oj.uz

Submission #1116503

# Submission time Handle Problem Language Result Execution time Memory
1116503 2024-11-21T18:13:18 Z staszic_ojuz The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 1 ms 504 KB 
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> m;
int inf = 2000000000;
int mini = 2000000000;
int h,w;
bool sigma(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 = j;
            }
            if(j >= jl)
            {
                max2 = max(max2,m[i][j]);
                min2 = min(min2,m[i][j]);
            }
        }
    }
    //cout<<max2<<" "<<min2<<" "<<jl<<"\n";
    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(sigma(mid))
        {
            r = mid;
        }
        else
        {
            l = mid;
        }
      //  cout<<mid<<"\n";
    }
    return l+1;
}
int main()
{
    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();
    //cout<<ans<<"\n"<<"\n";
    reverse(m.begin(),m.end());
    ans = min(ans,bs());
    //cout<<ans<<"\n"<<"\n";r
    for(int i = 0;i<h;i++)
    {
        reverse(m[i].begin(),m[i].end());
    }
    ans = min(ans,bs());
    //cout<<ans<<"\n"<<"\n";
    reverse(m.begin(),m.end());
    ans = min(ans,bs());
    cout<<ans;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Incorrect 1 ms 504 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Incorrect 1 ms 504 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Incorrect 1 ms 504 KB Output isn't correct
4 Halted 0 ms 0 KB -