제출 #379645

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
379645		penguinhacker	최솟값 배열 (IZhO11_hyper)	C++14	100 / 100	473 ms	57984 KiB

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 / 100