제출 #733130

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
733130		ac2hu	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	624 ms	70688 KiB

joioi

#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++)f[i] = min(f[i],f[i - 1]);
                if(check2(f, siz)){
                    return true;
                }
                f = c;for(int i = H - 2;i>=0;i--)f[i] = min(f[i], f[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++)f[i] = max(f[i],f[i - 1]);
                if(check3(f, siz)){
                    return true;
                }
                f = c;for(int i = H - 2;i>=0;i--)f[i] = max(f[i], f[i + 1]);
                if(check3(f, siz)){
                    return true;
                }
            }
        }
        return false;
    };
    int l = 0, r = 1e9 + 1e8;
    while(l < r){
        int mid = (l + r - 1)/2;
        if(check(mid))r = mid;
        else l = mid + 1;
    }
    cout << l << "\n";
}

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