Submission #73271148

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
#define INF 1010101010
int cmp(const void* x, const void* y) {
  int a = *(const int*)x, b = *(const int*)y;
  return (a > b) - (a < b);
}
struct q_s {
  int x, y, level;
};
int qc = 0, qs = 0;
struct q_s* q;
void qadjust(int pos) {
  for (;;) {
    int i;
    int minpos = pos;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>

#define INF 1010101010

int cmp(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return (a > b) - (a < b);
}

struct q_s {
	int x, y, level;
};

int qc = 0, qs = 0;
struct q_s* q;

void qadjust(int pos) {
	for (;;) {
		int i;
		int minpos = pos;
		for (i = 1; i <= 2; i++) {
			int c = pos * 2 + i;
			if (c < qs && q[c].level < q[minpos].level) minpos = c;
		}
		if (minpos == pos) {
			if (pos == 0) return;
			pos = (pos - 1) / 2;
		} else {
			struct q_s t = q[pos];
			q[pos] = q[minpos];
			q[minpos] = t;
			pos = minpos;
		}
	}
}

void qadd(struct q_s data) {
	if (qs >= qc) {
		q = realloc(q, sizeof(*q) * (qc = qs + 1));
		if (q == NULL) exit(2);
	}
	q[qs++] = data;
	qadjust(qs - 1);
}

struct q_s qget(void) {
	struct q_s res;
	if (qs <= 0) exit(72);
	res = q[0];
	if (--qs > 0) {
		q[0] = q[qs];
		qadjust(0);
	}
	return res;
}

/* tiisaku nai hou */
int tnh(int a, int b) {
	return a >= b ? a : b;
}

void calc(int levels[], int minlevel[512][512], int L[512][512], int W, int H, int X, int Y) {
	int i, j;
	for (i = 1; i <= H; i++) {
		for (j = 1; j <= W; j++) minlevel[i][j] = INF;
	}
	qs = 0;
	minlevel[Y][X] = L[Y][X];
	qadd((struct q_s){ X, Y, L[Y][X] });
	while (qs > 0) {
		struct q_s cur = qget();
		if (cur.level == minlevel[cur.y][cur.x]) {
			for (i = 0; i < 4; i++) {
				int ny = cur.y + (i < 2) * ((i & 1) * 2 - 1);
				int nx = cur.x + (i >= 2) * ((i & 1) * 2 - 1);
				if (1 <= ny && ny <= H &&1 <= nx && nx <= W) {
					int next_level = tnh(cur.level, L[ny][nx]);
					if (minlevel[ny][nx] > next_level) {
						minlevel[ny][nx] = next_level;
						qadd((struct q_s){ nx, ny, next_level });
					}
				}
			}
		}
	}
	for (i = 0; i < H; i++) {
		for (j = 0; j < W; j++) {
			levels[i * W + j + 1] = minlevel[i + 1][j + 1];
		}
	}
	qsort(levels + 1, W * H, sizeof(*levels), cmp);
	levels[0] = 0;
}

int R;
int W1, H1, X1, Y1;
int L1[512][512];
int W2, H2, X2, Y2;
int L2[512][512];

int minlevel1[512][512], minlevel2[512][512];

int levels1[512 * 512], levels2[512 * 512];

int main(void) {
	int i, j;
	int ans = INF;
	if (scanf("%d", &R) != 1) return 1;
	if (scanf("%d%d%d%d", &W1, &H1, &X1, &Y1) != 4) return 1;
	for (i = 1; i <= H1; i++) {
		for (j = 1; j <= W1; j++) {
			if (scanf("%d", &L1[i][j]) != 1) return 1;
		}
	}
	if (scanf("%d%d%d%d", &W2, &H2, &X2, &Y2) != 4) return 1;
	for (i = 1; i <= H2; i++) {
		for (j = 1; j <= W2; j++) {
			if (scanf("%d", &L2[i][j]) != 1) return 1;
		}
	}
	calc(levels1, minlevel1, L1, W1, H1, X1, Y1);
	calc(levels2, minlevel2, L2, W2, H2, X2, Y2);
	for (i = 0; i <= W1 * H1; i++) {
		int left = R - i;
		if (left <= W2 * H2) {
			int score = levels1[i];
			if (left >= 0) score += levels2[left];
			if (score < ans) ans = score;
		}
	}
	printf("%d\n", ans);
	return 0;
}

Submission Info

Judge Result