답안 #379645

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
379645	2021-03-19T01:04:49 Z	penguinhacker	최솟값 배열 (IZhO11_hyper)	C++14	100 / 100	473 ms	57984 KB

hyper

// source: https://oj.uz/problem/view/IZhO11_hyper
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN = 35;
int n, m, a[mxN][mxN][mxN][mxN], dp[mxN][mxN][mxN][mxN], dp2[mxN][mxN][mxN][mxN], dp3[mxN][mxN][mxN][mxN], dp4[mxN][mxN][mxN][mxN];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			for (int k = 0; k < n; ++k)
				for (int l = 0; l < n; ++l)
					cin >> a[i][j][k][l];
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			for (int k = 0; k < n; ++k) {
				deque<int> dq;
				for (int l = 0; l < n; ++l) {
					while(!dq.empty() && a[i][j][k][l] <= a[i][j][k][dq.back()])
						dq.pop_back();
					if (!dq.empty() && l >= m && dq[0] == l - m)
						dq.pop_front();
					dq.push_back(l);
					dp[i][j][k][l] = a[i][j][k][dq[0]];
				}
			}
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			for (int l = m - 1; l < n; ++l) {
				deque<int> dq;
				for (int k = 0; k < n; ++k) {
					while(!dq.empty() && dp[i][j][k][l] <= dp[i][j][dq.back()][l])
						dq.pop_back();
					if (!dq.empty() && k >= m && dq[0] == k - m)
						dq.pop_front();
					dq.push_back(k);
					dp2[i][j][k][l] = dp[i][j][dq[0]][l];
				}
			}
	for (int i = 0; i < n; ++i)
		for (int k = m - 1; k < n; ++k)
			for (int l = m - 1; l < n; ++l) {
				deque<int> dq;
				for (int j = 0; j < n; ++j) {
					while(!dq.empty() && dp2[i][j][k][l] <= dp2[i][dq.back()][k][l])
						dq.pop_back();
					if (!dq.empty() && j >= m && dq[0] == j - m)
						dq.pop_front();
					dq.push_back(j);
					dp3[i][j][k][l] = dp2[i][dq[0]][k][l];
				}
			}
	for (int j = m - 1; j < n; ++j)
		for (int k = m - 1; k < n; ++k)
			for (int l = m - 1; l < n; ++l) {
				deque<int> dq;
				for (int i = 0; i < n; ++i) {
					while(!dq.empty() && dp3[i][j][k][l] <= dp3[dq.back()][j][k][l])
						dq.pop_back();
					if (!dq.empty() && i >= m && dq[0] == i - m)
						dq.pop_front();
					dq.push_back(i);
					dp4[i][j][k][l] = dp3[dq[0]][j][k][l];
				}
			}
	for (int i = m - 1; i < n; ++i)
		for (int j = m - 1; j < n; ++j)
			for (int k = m - 1; k < n; ++k)
				for (int l = m - 1; l < n; ++l)
					cout << dp4[i][j][k][l] << " ";
	return 0;
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	876 KB	Output is correct
3	Correct	3 ms	2412 KB	Output is correct
4	Correct	4 ms	2680 KB	Output is correct
5	Correct	4 ms	2924 KB	Output is correct
6	Correct	15 ms	6380 KB	Output is correct
7	Correct	14 ms	5612 KB	Output is correct
8	Correct	29 ms	9836 KB	Output is correct
9	Correct	59 ms	13420 KB	Output is correct
10	Correct	31 ms	10604 KB	Output is correct
11	Correct	86 ms	19308 KB	Output is correct
12	Correct	165 ms	30060 KB	Output is correct
13	Correct	130 ms	25836 KB	Output is correct
14	Correct	231 ms	36076 KB	Output is correct
15	Correct	376 ms	50668 KB	Output is correct
16	Correct	187 ms	34668 KB	Output is correct
17	Correct	228 ms	38252 KB	Output is correct
18	Correct	473 ms	57984 KB	Output is correct
19	Correct	299 ms	44908 KB	Output is correct
20	Correct	234 ms	39020 KB	Output is correct