풀이
#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() {
collect();
charge();
reset_BC();
for (int i = 0; i < M; i++) {
move(A_mv[i], Ax, Ay);
move(B_mv[i], Bx, By);
collect();
if (is_duplicated()) {
if (A_BC.size() && B_BC.size()) {
compare_charge_amount();
}
else {
charge();
}
}
else {
charge();
}
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;
}