Submission #4852

#	Time	Username	Problem	Language	Result	Execution time	Memory
4852		tncks0121	Hyper-minimum (IZhO11_hyper)	C++98	85 / 100	444 ms	30548 KiB

hyper

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <memory.h> 
#include <math.h> 
#include <assert.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <string> 
#include <functional> 
#include <vector> 
#include <deque> 
#include <utility> 
#include <bitset> 
#include <limits.h>  
#include <time.h>

using namespace std; 
typedef long long ll; 
typedef unsigned long long llu; 
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

#define FOR1(i, s, e) for(int i = (s); i <= (e); i++)
#define FOR2(i, j, s, e) FOR1(i, s, e) FOR1(j, s, e)
#define FOR3(i, j, k, s, e) FOR1(i, s, e) FOR1(j, s, e) FOR1(k, s, e)
#define FOR4(i, j, k, l, s, e) FOR1(i, s, e) FOR1(j, s, e) FOR1(k, s, e) FOR1(l, s, e)

int N, M, K;
int X[35][35][35][35];

int R1[35][35][35][35];
int R2[35][35][35][35];
int R3[35][35][35][35];
int R4[35][35][35][35];
int tmp1[35], tmp2[35];

deque<pii> deq;
void fillmin (int *to, int *A) {
	while(!deq.empty()) deq.pop_back();
	FOR1(i, 1, N) {
		while(!deq.empty() && deq.back().first > A[i]) deq.pop_back();
		deq.push_back(pii(A[i], i));
		while(!deq.empty() && deq.front().second <= i-M) deq.pop_front();
		if(i >= M) to[i-M+1] = deq.front().first;
	}
}

int main() {
	int i, j, k;
	
	scanf("%d%d", &N, &M);
	FOR4(i1, i2, i3, i4, 1, N) scanf("%d", &X[i1][i2][i3][i4]);
	K = N-M+1;

	FOR3(i1, i2, i3, 1, N) {
		fillmin(R1[i1][i2][i3], X[i1][i2][i3]);
	}

	FOR2(i1, i2, 1, N) FOR1(i4, 1, K) {
		FOR1(i3, 1, N) tmp1[i3] = R1[i1][i2][i3][i4];
		fillmin(tmp2, tmp1);
		FOR1(i3, 1, K) R2[i1][i2][i3][i4] = tmp2[i3];
	}

	FOR1(i1, 1, N) FOR2(i3, i4, 1, K) {
		FOR1(i2, 1, N) tmp1[i2] = R2[i1][i2][i3][i4];
		fillmin(tmp2, tmp1);
		FOR1(i2, 1, K) R3[i1][i2][i3][i4] = tmp2[i2];
	}

	FOR3(i2, i3, i4, 1, K) {
		FOR1(i1, 1, N) tmp1[i1] = R3[i1][i2][i3][i4];
		fillmin(tmp2, tmp1);
		FOR1(i1, 1, K) R4[i1][i2][i3][i4] = tmp2[i1];
	}

	FOR4(i1, i2, i3, i4, 1, K) printf("%d ", R4[i1][i2][i3][i4]);
	return 0;
}

• Subtask 1: 85 / 100