oj.uz

Submission #46722

# Submission time Handle Problem Language Result Execution time Memory
46722 2018-04-22T15:53:20 Z maksim_gaponov The Kingdom of JOIOI (JOI17_joioi) C++14
15 / 100
 4000 ms 712 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 116 ms 460 KB Output is correct
4 Correct 53 ms 472 KB Output is correct
5 Correct 114 ms 472 KB Output is correct
6 Correct 23 ms 524 KB Output is correct
7 Correct 118 ms 672 KB Output is correct
8 Correct 113 ms 672 KB Output is correct
9 Correct 114 ms 672 KB Output is correct
10 Correct 118 ms 672 KB Output is correct
11 Correct 119 ms 712 KB Output is correct
12 Correct 124 ms 712 KB Output is correct
13 Correct 118 ms 712 KB Output is correct
14 Correct 116 ms 712 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 116 ms 460 KB Output is correct
4 Correct 53 ms 472 KB Output is correct
5 Correct 114 ms 472 KB Output is correct
6 Correct 23 ms 524 KB Output is correct
7 Correct 118 ms 672 KB Output is correct
8 Correct 113 ms 672 KB Output is correct
9 Correct 114 ms 672 KB Output is correct
10 Correct 118 ms 672 KB Output is correct
11 Correct 119 ms 712 KB Output is correct
12 Correct 124 ms 712 KB Output is correct
13 Correct 118 ms 712 KB Output is correct
14 Correct 116 ms 712 KB Output is correct
15 Execution timed out 4008 ms 712 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 116 ms 460 KB Output is correct
4 Correct 53 ms 472 KB Output is correct
5 Correct 114 ms 472 KB Output is correct
6 Correct 23 ms 524 KB Output is correct
7 Correct 118 ms 672 KB Output is correct
8 Correct 113 ms 672 KB Output is correct
9 Correct 114 ms 672 KB Output is correct
10 Correct 118 ms 672 KB Output is correct
11 Correct 119 ms 712 KB Output is correct
12 Correct 124 ms 712 KB Output is correct
13 Correct 118 ms 712 KB Output is correct
14 Correct 116 ms 712 KB Output is correct
15 Execution timed out 4008 ms 712 KB Time limit exceeded
16 Halted 0 ms 0 KB -