oj.uz

Submission #4852

# Submission time Handle Problem Language Result Execution time Memory
4852 2014-01-05T08:57:39 Z tncks0121 Hyper-minimum (IZhO11_hyper) C++
85 / 100
 444 ms 30548 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[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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 30548 KB Output is correct
2 Correct 0 ms 30548 KB Output is correct
3 Correct 0 ms 30548 KB Output is correct
4 Correct 0 ms 30548 KB Output is correct
5 Correct 4 ms 30548 KB Output is correct
6 Correct 16 ms 30548 KB Output is correct
7 Correct 4 ms 30548 KB Output is correct
8 Correct 28 ms 30548 KB Output is correct
9 Correct 56 ms 30548 KB Output is correct
10 Correct 28 ms 30548 KB Output is correct
11 Correct 100 ms 30548 KB Output is correct
12 Correct 172 ms 30548 KB Output is correct
13 Correct 148 ms 30548 KB Output is correct
14 Correct 284 ms 30548 KB Output is correct
15 Correct 444 ms 30548 KB Output is correct
16 Correct 224 ms 30548 KB Output is correct
17 Correct 264 ms 30548 KB Output is correct
18 Incorrect 256 ms 30544 KB Output isn't correct
19 Incorrect 256 ms 30544 KB Output isn't correct
20 Runtime error 244 ms 30544 KB futex (syscall #202) was called by the program (disallowed syscall)