Submission #1157923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157923		dnnnda	The Kingdom of JOIOI (JOI17_joioi)	C++20	15 / 100	4094 ms	328 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define ll long long
//#define int long long
//#pragma GCC optimize("Ofast, unroll-loop")
//#pragma GCC target("avx,avx2")
#pragma GCC optimize("O3")
const int inf=0x3f3f3f3f;
const ll inff=0x3f3f3f3f3f3f3f3f;
//const int X=1000000007;
const int X=998244353;

int a[15][15], ans=inf, h, w, mx, mn=inf;
vector<int> v;
void dfs(int ht, int t){
    v.push_back(ht);
    if(v.size()==w){
        int mn1=inf, mx1=0, mn2=inf, mx2=0;
        for(int i=0 ; i<h ; i++) for(int j=0 ; j<w ; j++){
            if(i<v[j]) mn1=min(mn1,a[i][j]), mx1=max(mx1,a[i][j]);
            else mn2=min(mn2,a[i][j]), mx2=max(mx2,a[i][j]);
        }
        ans=min(ans,max(mx2-mn2,mx1-mn1));
    }
    else{
        for(int i=ht ; 0<=i&&i<=h ; i+=t){
            dfs(i,t);
        }
    }
    v.pop_back();
    return;
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> h >> w;
    for(int i=0 ; i<h ; i++) for(int j=0 ; j<w ; j++){
        cin >> a[i][j];
        mn=min(mn,a[i][j]);
        mx=max(mx,a[i][j]);
    }
    ans=mx-mn;
    for(int i=0 ; i<=h ; i++) dfs(i,1), dfs(i,-1);
    cout << ans << '\n';

    return 0;
}

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