oj.uz

Submission #4853

# Submission time Handle Problem Language Result Execution time Memory
4853 2014-01-05T08:59:33 Z tncks0121 Hyper-minimum (IZhO11_hyper) C++
100 / 100
 532 ms 123308 KB 
#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[50][50][50][50];

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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 123308 KB Output is correct
2 Correct 0 ms 123308 KB Output is correct
3 Correct 0 ms 123308 KB Output is correct
4 Correct 4 ms 123308 KB Output is correct
5 Correct 0 ms 123308 KB Output is correct
6 Correct 12 ms 123308 KB Output is correct
7 Correct 12 ms 123308 KB Output is correct
8 Correct 32 ms 123308 KB Output is correct
9 Correct 68 ms 123308 KB Output is correct
10 Correct 36 ms 123308 KB Output is correct
11 Correct 76 ms 123308 KB Output is correct
12 Correct 196 ms 123308 KB Output is correct
13 Correct 148 ms 123308 KB Output is correct
14 Correct 280 ms 123308 KB Output is correct
15 Correct 444 ms 123308 KB Output is correct
16 Correct 244 ms 123308 KB Output is correct
17 Correct 280 ms 123308 KB Output is correct
18 Correct 532 ms 123308 KB Output is correct
19 Correct 332 ms 123308 KB Output is correct
20 Correct 292 ms 123308 KB Output is correct