[SWEA] 5644. 무선충전

풀이

#include <iostream>
#include <vector>
#include <queue>
#include <math.h>

using namespace std;

typedef struct BC {
	int x;
	int y;
	int C;
	int P;
	int num;
} BC;

int T, M, A;
int Ax, Ay, Bx, By;
vector<BC> A_BC, B_BC;
int A_mv[100];
int B_mv[100];
BC BC_list[8];
vector <int> RST;
int SUM;

void init() {
	cin >> M >> A;
	for (int i = 0; i < M; i++) {
		cin >> A_mv[i];
	}
	for (int i = 0; i < M; i++) {
		cin >> B_mv[i];
	}
	for (int i = 0; i < A; i++) {
		BC bc;
		cin >> bc.x >> bc.y >> bc.C >> bc.P;
		bc.num = i + 1;
		BC_list[i] = bc;
	}	
	Ax = 1; Ay = 1; Bx = 10; By = 10;
	SUM = 0;
}


void move(int dir, int &x, int &y) {
	switch (dir) {
	case 0:
		break;
	case 1:
		y--;
		break;
	case 2:
		x++;
		break;
	case 3:
		y++;
		break;
	case 4:
		x--;
		break;
	}
}

void collect() {
	for (int i = 0; i < A; i++) {
		if (abs(BC_list[i].x - Ax) + abs(BC_list[i].y - Ay) <= BC_list[i].C) {
			A_BC.push_back(BC_list[i]);
		}
		if (abs(BC_list[i].x - Bx) + abs(BC_list[i].y - By) <= BC_list[i].C) {
			B_BC.push_back(BC_list[i]);
		}
	}
}

void reset_BC() {
	while (A_BC.size()) {
		A_BC.pop_back();
	}
	while (B_BC.size()) {
		B_BC.pop_back();
	}
}

void charge() {
	int max = 0;
	for (int i = 0; i < A_BC.size(); i++) {
		if (A_BC[i].P > max) max = A_BC[i].P;
	}
	SUM += max;
	max = 0;
	for (int i = 0; i < B_BC.size(); i++) {
		if (B_BC[i].P > max) max = B_BC[i].P;
	}
	SUM += max;
}

void compare_charge_amount() {
	int PA, PB;
	int sum = 0;
	for (int i = 0; i < A_BC.size(); i++) {
		PA = A_BC[i].P;
		for (int j = 0; j < B_BC.size(); j++) {
			PB = B_BC[j].P;
			if(A_BC[i].num == B_BC[j].num){
				if (PA > sum) {
					sum = PA;
				}
			}
			else {
				if (PA + PB > sum) sum = PA + PB;
			}
		}
	}
	SUM += sum;
}

int is_duplicated() {
	for (int i = 0; i < A_BC.size(); i++) {
		for (int j = 0; j < B_BC.size(); j++) {
			if (A_BC[i].num == B_BC[j].num) return 1;
		}
	}
	return 0;
}

void solve() {
	// 0. initial charge
	collect();
	charge();
	reset_BC();

	for (int i = 0; i < M; i++) {
		// 1. move
		move(A_mv[i], Ax, Ay);
		move(B_mv[i], Bx, By);

		// 2. collect BC data in current position
		collect();
			
		// 3. check position duplicated
		if (is_duplicated()) {
			if (A_BC.size() && B_BC.size()) {
				compare_charge_amount();
			}
			else {
				charge();
			}
		}
		else {
			charge();
		}
		// 4. reset
		reset_BC();
	}	
}

int main() {
	cin >> T;
	for (int tc = 0; tc < T; tc++) {
		init();
		solve();
		RST.push_back(SUM);
	}
	for (int tc = 0; tc < T; tc++) {
		cout << "#" << tc + 1 << " " << RST[tc] << endl;
	}
    return 0;
}

Tip

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