oj.uz

Submission #733122

# Submission time Handle Problem Language Result Execution time Memory
733122 2023-04-30T06:43:32 Z ac2hu The Kingdom of JOIOI (JOI17_joioi) C++14
0 / 100
 0 ms 212 KB 
#include <bits/stdc++.h>
#ifdef DEBUG
#include "../templates/debug.h"
#else 
#define deb(x...)
#endif
using namespace std;
#define int long long 
signed main() {
    iostream::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int H, W;cin >> H >> W;
    int v = -1, x = -1, y = -1;
    vector<vector<int>> a(H, vector<int>(W));
    for(int i = 0;i<H;i++){
        for(int j = 0;j<W;j++){
            cin >> a[i][j];
            if(a[i][j] > v)v = a[i][j], x = i, y = j;
        }
    }
    auto check2 = [&](vector<int> v, int siz){
        int mn = 1e9, mx = -1e9;
        for(int i = 0;i<H;i++){
            for(int j = W - 1;j>v[i];j--){
                mn = min(mn, a[i][j]);
                mx = max(mx, a[i][j]);
            }
        }
        if(mx - mn <= siz)return true;
        else return false;
    };
    auto check3 = [&](vector<int> v, int siz){
        int mn = 1e9, mx = -1e9;
        for(int i = 0;i<H;i++){
            for(int j = 0;j<v[i];j++){
                mn = min(mn, a[i][j]);
                mx = max(mx, a[i][j]);
            }
        }
        if(mx - mn <= siz)return true;
        else return false;
    };
    auto check = [&](int siz){
        int maximum = v;
        {
            // Case1: build it from 0 onwards
            vector<int> c;
            for(int i = 0;i<H;i++){
                bool used = false;
                for(int j = 0;j<W;j++){
                    if(maximum - a[i][j] > siz){
                        c.push_back(j - 1);
                        used = true;
                        break;
                    }
                }
                if(!used)c.push_back(W - 1);
            } 
            if(c[x] >= y){
                vector<int> f = c;
                for(int i = 1;i<H;i++)c[i] = min(c[i],c[i - 1]);
                if(check2(f, siz)){
                    return true;
                }
                f = c;for(int i = H - 2;i>=0;i--)c[i] = min(c[i], c[i + 1]);
                if(check2(f, siz)){
                    return true;
                }
            }
        }
        {

            // Case2: build it fron W - 1
            vector<int> c;
            for(int i = 0;i<H;i++){
                bool used = false;
                for(int j = W - 1;j>=0;j--){
                    if(maximum - a[i][j] > siz){
                        c.push_back(j + 1);
                        used = true;
                        break;
                    }
                }
                if(!used)c.push_back(0);
            } 
            if(c[x] <= y){
                vector<int> f = c;
                for(int i = 1;i<H;i++)c[i] = max(c[i],c[i - 1]);
                if(check3(f, siz)){
                    return true;
                }
                f = c;for(int i = H - 2;i>=0;i--)c[i] = max(c[i], c[i + 1]);
                if(check3(f, siz)){
                    return true;
                }
            }
        }
        return false;
    };
    int l = 0, r = 1e9;
    while(l < r){
        int mid = (l + r - 1)/2;
        if(check(mid))r = mid;
        else l = mid + 1;
    }
    cout << l << "\n";
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -