Submission #379971

#	Time	Username	Problem	Language	Result	Execution time	Memory
379971		rainboy	Land of the Rainbow Gold (APIO17_rainbow)	C11	38 / 100	124 ms	19692 KiB

rainbow

#include "rainbow.h"

#define N	1000
#define M	1000

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int vv[N][M], ee1[N][M], ee2[N][M], ff[N][M], imin, imax, jmin, jmax;

void init(int n, int m, int i_, int j_, int l, char *dd) {
	int h, i, j;

	i_--, j_--;
	if (n > 1000 || m > 1000)	/* :( */
		return;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			vv[i][j] = 1;
	imin = imax = i_, jmin = jmax = j_;
	vv[i_][j_] = 0;
	for (h = 0; h < l; h++) {
		if (dd[h] == 'N')
			i_--;
		else if (dd[h] == 'S')
			i_++;
		else if (dd[h] == 'W')
			j_--;
		else
			j_++;
		imin = min(imin, i_), imax = max(imax, i_);
		jmin = min(jmin, j_), jmax = max(jmax, j_);
		vv[i_][j_] = 0;
	}
	for (i = 0; i < n; i++)
		for (j = 1; j < m; j++)
			ee1[i][j] = vv[i][j] && vv[i][j - 1];
	for (i = 1; i < n; i++)
		for (j = 0; j < m; j++)
			ee2[i][j] = vv[i][j] && vv[i - 1][j];
	for (i = 1; i < n; i++)
		for (j = 1; j < m; j++)
			ff[i][j] = vv[i][j] && vv[i][j - 1] && vv[i - 1][j] && vv[i - 1][j - 1];
	for (i = 0; i < n; i++)
		for (j = 1; j < m; j++)
			vv[i][j] += vv[i][j - 1];
	for (j = 0; j < m; j++)
		for (i = 1; i < n; i++)
			vv[i][j] += vv[i - 1][j];
	for (i = 0; i < n; i++)
		for (j = 1; j < m; j++)
			ee1[i][j] += ee1[i][j - 1];
	for (j = 0; j < m; j++)
		for (i = 1; i < n; i++)
			ee1[i][j] += ee1[i - 1][j];
	for (i = 0; i < n; i++)
		for (j = 1; j < m; j++)
			ee2[i][j] += ee2[i][j - 1];
	for (j = 0; j < m; j++)
		for (i = 1; i < n; i++)
			ee2[i][j] += ee2[i - 1][j];
	for (i = 0; i < n; i++)
		for (j = 1; j < m; j++)
			ff[i][j] += ff[i][j - 1];
	for (j = 0; j < m; j++)
		for (i = 1; i < n; i++)
			ff[i][j] += ff[i - 1][j];
}

int rect(int aa[][M], int i1, int j1, int i2, int j2) {
	return i1 > i2 || j1 > j2 ? 0 : aa[i2][j2] - (j1 == 0 ? 0 : aa[i2][j1 - 1]) - (i1 == 0 ? 0 : aa[i1 - 1][j2]) + (i1 == 0 || j1 == 0 ? 0 : aa[i1 - 1][j1 - 1]);
}

int colour(int i1, int j1, int i2, int j2) {
	int v, e, f;

	i1--, j1--, i2--, j2--;
	v = rect(vv, i1, j1, i2, j2);
	e = rect(ee1, i1, j1 + 1, i2, j2) + rect(ee2, i1 + 1, j1, i2, j2);
	f = rect(ff, i1 + 1, j1 + 1, i2, j2);
	if (i1 < imin && imax < i2 && j1 < jmin && jmax < j2)
		f++;
	return v - e + f;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 27 / 27
• Subtask 5: 0 / 26