Submission #46722

#	Time	Username	Problem	Language	Result	Execution time	Memory
46722		maksim_gaponov	The Kingdom of JOIOI (JOI17_joioi)	C++14	15 / 100	4008 ms	712 KiB

joioi

#define _CRT_SECURE_NO_WARNINGS
#ifdef KEK
#define FILE_IN "input.txt"
#define FILE_OUT "output.txt"
#endif
#include <iostream>
#include <cstdlib>
#include <climits>
#include <set>
#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;

void openFiles() {
#ifdef KEK
	assert(freopen(FILE_IN, "r", stdin));
	assert(freopen(FILE_OUT, "w", stdout));
#endif
}

const int MAXH = 12;
const int INF = INT_MAX;
int a[MAXH][MAXH];
int x[MAXH];
int h, w;
int ans = INF;

void solve() {
    memset(x, 0, sizeof(x));
    x[w - 1] = 1;
    while (true) {
        int mx[2] = {-INF, -INF};
        int mn[2] = {INF, INF};
        bool need_stop = true;
        for (int i = 0; i < w; i++) {
            //cout << x[i] << " ";
            if (x[i] != h)
                need_stop = false;
        }
        //cout << "\n";
        if (need_stop)
            break;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                int type = (x[j] > i);
                mx[type] = max(mx[type], a[i][j]);
                mn[type] = min(mn[type], a[i][j]);
            }
        }
        int res1 = mx[0] - mn[0];
        int res2 = mx[1] - mn[1];
        int new_ans = max(res1, res2);
        //cout << new_ans << "\n";
        ans = min(ans, new_ans);
        x[w - 1]++;
        int pos = w - 1;
        while (pos > 0 && x[pos] == h + 1) {
            x[pos - 1]++;
            for (int i = pos; i < w; i++) {
                x[i] = x[pos - 1];
            }
            pos--;
        }
        if (x[0] == h + 1) {
            break;
        }
    }
}

void magic() {
    for (int i = 0; i < h; i++) {
        for (int j = 0; 2 * j < w; j++) {
            swap(a[i][j], a[i][w - j - 1]);
        }
    }
}

int main() {
	openFiles();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    cin >> h >> w;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> a[i][j];
        }
    }
    solve();
    magic();
    solve();
    cout << ans;
	return 0;
}

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