답안 #913558

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
913558	2024-01-20T08:21:28 Z	daoquanglinh2007	최솟값 배열 (IZhO11_hyper)	C++17	100 / 100	271 ms	65096 KB

hyper

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

const int NM = 35;

int N, M, a[NM+5][NM+5][NM+5][NM+5];
int f1[NM+5][NM+5][NM+5][NM+5], f2[NM+5][NM+5][NM+5][NM+5], f3[NM+5][NM+5][NM+5][NM+5], f4[NM+5][NM+5][NM+5][NM+5];
deque <int> dq;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			for (int k = 1; k <= N; k++)
				for (int l = 1; l <= N; l++)
					cin >> a[i][j][k][l];
					
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			for (int k = 1; k <= N; k++){
				dq.clear();
				for (int l = 1; l <= N; l++){
					if (l > M && dq.front() == l-M) dq.pop_front();
					while (!dq.empty() && a[i][j][k][l] <= a[i][j][k][dq.back()]) dq.pop_back();
					dq.push_back(l);
					if (l >= M) f1[i][j][k][l] = a[i][j][k][dq.front()];
				}
			}
			
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			for (int l = M; l <= N; l++){
				dq.clear();
				for (int k = 1; k <= N; k++){
					if (k > M && dq.front() == k-M) dq.pop_front();
					while (!dq.empty() && f1[i][j][k][l] <= f1[i][j][dq.back()][l]) dq.pop_back();
					dq.push_back(k);
					if (k >= M) f2[i][j][k][l] = f1[i][j][dq.front()][l];
				}
			}
	for (int i = 1; i <= N; i++)
		for (int k = M; k <= N; k++)
			for (int l = M; l <= N; l++){
				dq.clear();
				for (int j = 1; j <= N; j++){
					if (j > M && dq.front() == j-M) dq.pop_front();
					while (!dq.empty() && f2[i][j][k][l] <= f2[i][dq.back()][k][l]) dq.pop_back();
					dq.push_back(j);
					if (j >= M) f3[i][j][k][l] = f2[i][dq.front()][k][l];
				}
			}
	for (int j = M; j <= N; j++)
		for (int k = M; k <= N; k++)
			for (int l = M; l <= N; l++){
				dq.clear();
				for (int i = 1; i <= N; i++){
					if (i > M && dq.front() == i-M) dq.pop_front();
					while (!dq.empty() && f3[i][j][k][l] <= f3[dq.back()][j][k][l]) dq.pop_back();
					dq.push_back(i);
					if (i >= M) f4[i][j][k][l] = f3[dq.front()][j][k][l];
				}
			}
	for (int i = M; i <= N; i++)
		for (int j = M; j <= N; j++)
			for (int k = M; k <= N; k++)
				for (int l = M; l <= N; l++)
					cout << f4[i][j][k][l] << ' ';
					
	return 0;
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10588 KB	Output is correct
2	Correct	3 ms	18780 KB	Output is correct
3	Correct	5 ms	20828 KB	Output is correct
4	Correct	6 ms	22996 KB	Output is correct
5	Correct	6 ms	23380 KB	Output is correct
6	Correct	13 ms	29276 KB	Output is correct
7	Correct	12 ms	26972 KB	Output is correct
8	Correct	22 ms	33264 KB	Output is correct
9	Correct	44 ms	38996 KB	Output is correct
10	Correct	25 ms	35152 KB	Output is correct
11	Correct	59 ms	39916 KB	Output is correct
12	Correct	108 ms	48588 KB	Output is correct
13	Correct	113 ms	41416 KB	Output is correct
14	Correct	209 ms	55364 KB	Output is correct
15	Correct	255 ms	61260 KB	Output is correct
16	Correct	136 ms	43456 KB	Output is correct
17	Correct	152 ms	49152 KB	Output is correct
18	Correct	271 ms	62940 KB	Output is correct
19	Correct	211 ms	65096 KB	Output is correct
20	Correct	162 ms	56776 KB	Output is correct