Submission #332867

#	Time	Username	Problem	Language	Result	Execution time	Memory
332867		limabeans	The Kingdom of JOIOI (JOI17_joioi)	C++17	15 / 100	4059 ms	492 KiB

joioi

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll inf = 1e18;
const int maxn = 2020;


int n,m;
ll g[maxn][maxn];
ll tmp[maxn][maxn];



ll dfs(int r, int hi, ll lo1, ll hi1, ll lo2, ll hi2) {
    if (r==n) {
	return max(hi1-lo1, hi2-lo2);
    }

    ll res = inf;
    for (int i=hi; i>=0; i--) {
	ll a = lo1;
	ll b = hi1;
	ll c = lo2;
	ll d = hi2;
	for (int j=0; j<m; j++) {
	    if (j<i) {
		a = min(a,g[r][j]);
		b = max(b,g[r][j]);
	    } else {
		c = min(c,g[r][j]);
		d = max(d,g[r][j]);
	    }
	}
	res = min(res, dfs(r+1,i,a,b,c,d));
    }
    return res;
}
   

ll solve() {
    return dfs(0,m,inf,-inf,inf,-inf);
}


void flipY() {
    for (int i=0; i<n; i++) {
	for (int j=0; j<m/2; j++) {
	    swap(g[i][j],g[i][m-j-1]);
	}
    }
}

void transpose() {
    for (int i=0; i<n; i++) {
	for (int j=0; j<m; j++) {
	    tmp[j][i]=g[i][j];
	}
    }
    swap(n,m);
    for (int i=0; i<n; i++) {
	for (int j=0; j<m; j++) {
	    g[i][j]=tmp[i][j];
	}
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);


    cin>>n>>m;
    for (int i=0; i<n; i++) {
	for (int j=0; j<m; j++) {
	    cin>>g[i][j];
	}
    }

    ll res = inf;
    res = min(res, solve());
    flipY();
    res = min(res, solve());
    flipY(); transpose();
    res = min(res, solve());
    flipY();
    res = min(res, solve());

    cout<<res<<endl;
    
    return 0;
}

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