제출 #97202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97202		E869120	무지개나라 (APIO17_rainbow)	C++14	12 / 100	136 ms	99908 KiB

rainbow

#include "rainbow.h"
#include <iostream>
#include <vector>
using namespace std;

vector<bool> used[2009]; int H, W;
vector<int> A[4][2009], A2[2009], A3[2009], A4[2009];

void init(int R, int C, int sr, int sc, int M, char *S) {
	H = R; W = C;
	for (int i = 0; i <= H; i++) used[i].resize(W + 1, true);
	for (int i = 0; i <= H; i++) { for (int j = 0; j < 4; j++) A[j][i].resize(W + 1, 0); }

	int cx = sr, cy = sc; used[cx][cy] = false;
	for (int i = 0; i < M; i++) {
		if (S[i] == 'E') cy++;
		if (S[i] == 'W') cy--;
		if (S[i] == 'N') cx--;
		if (S[i] == 'S') cx++;
		used[cx][cy] = false;
	}
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) { if (used[i][j] == true) A[0][i][j] = 1; }
	}
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W - 1; j++) { if (used[i][j] == true && used[i][j + 1] == true) A[1][i][j] = 1; }
	}
	for (int i = 1; i <= H - 1; i++) {
		for (int j = 1; j <= W; j++) { if (used[i][j] == true && used[i + 1][j] == true) A[2][i][j] = 1; }
	}
	for (int i = 1; i <= H - 1; i++) {
		for (int j = 1; j <= W - 1; j++) { if (used[i][j] == true && used[i][j + 1] == true && used[i + 1][j] == true && used[i + 1][j + 1] == true) A[3][i][j] = 1; }
	}
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j <= H; j++) {
			for (int k = 1; k <= W; k++) A[i][j][k] += A[i][j][k - 1];
		}
		for (int j = 1; j <= H; j++) {
			for (int k = 0; k <= W; k++) A[i][j][k] += A[i][j - 1][k];
		}
	}
}

int ranged(int ty, int px, int py, int qx, int qy) {
	if (px > qx || py > qy) return 0;
	return A[ty][px - 1][py - 1] + A[ty][qx][qy] - A[ty][px - 1][qy] - A[ty][qx][py - 1];
}

int colour(int ar, int ac, int br, int bc) {
	int Z1 = ranged(0, ar, ac, br, bc);
	int Z2 = ranged(1, ar, ac, br, bc - 1);
	int Z3 = ranged(2, ar, ac, br - 1, bc);
	int Z4 = ranged(3, ar, ac, br - 1, bc - 1);
	return (Z1 - Z2 - Z3 + Z4);
}

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