문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo

경우의 수 나누는 훈련을 하고 있는거 같다 (…)
– 0 (처음에 안 움직일 때)~ M (주어진 시간)까지 해서 M+1번 정보를 업데이트 해야됨.
– 0일 때 빼고는 이동 정보를 업데이트하고, 이후 사람A과 B가 접근할 수 있는 BC들의 목록을 정함
– 둘 다 접근할 수 있는 BC가 1개 이상이면 겹칠 가능성이 있으므로 모든 경우의 수를 계산하고, 한 명이라도 접근할 수 있는 BC가 0개인 경우 겹칠 일이 없으므로 파워가 가장 센 BC 선택

import java.io.*;
import java.util.*;

public class Solution {	
	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("./src/sample_input.txt"));
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			int numCases = Integer.parseInt(reader.readLine());
	
			for (int num = 0; num < numCases; num++) {
				writer.write("#" + String.valueOf(num + 1) + " ");

				// 기본 A, B 위치 
				int xUserA = 1, yUserA = 1;
				int xUserB = 10, yUserB = 10;

				String[] tmp = reader.readLine().split(" ");
				int numM = Integer.parseInt(tmp[0]); // 총 이동 시간
				int numA = Integer.parseInt(tmp[1]); // BC의 갯수
								
				// 사용자 A 이동 정보 (0: 이동 안함, 1: 상, 2: 우, 3: 하, 4: 좌)
				String[] tmp_ = reader.readLine().split(" ");
				int[] userA = new int[tmp_.length]; // 사용자 A의 이동 정보
				for (int i = 0; i < tmp_.length; i++)
					userA[i] = Integer.parseInt(tmp_[i]);
				
				// 사용자 B 이동 정보 (0: 이동 안함, 1: 상, 2: 우, 3: 하, 4: 좌)
				tmp_ = reader.readLine().split(" ");
				int[] userB = new int[tmp_.length]; // 사용자 B의 이동 정보
				for (int i = 0; i < tmp_.length; i++)
					userB[i] = Integer.parseInt(tmp_[i]);

				// BC 정보
				int[] xBC = new int[numA]; // 좌표 (X)
				int[] yBC = new int[numA]; // 좌표 (Y)
				int[] cBC = new int[numA]; // 충전 범위
				int[] pBC = new int[numA]; // 처리량
				
				for (int i = 0; i < numA; i++) {
					String[] tmp__ = reader.readLine().split(" ");
					
					xBC[i] = Integer.parseInt(tmp__[0]);
					yBC[i] = Integer.parseInt(tmp__[1]);
					cBC[i] = Integer.parseInt(tmp__[2]);
					pBC[i] = Integer.parseInt(tmp__[3]);
				}

				// 실제 최대 충전량 계산 
				int answer = 0;
				
				// -1: 움직이기 전, 0~numM-1: 움직이는 중 (0~numM 을 -1~numM-1 로 환산)
				for (int i = -1; i < numM; i++) {
//					// 움직이는 경우 (i == -1이면 이동할 필요가 없음)
					if (i != -1) {
						switch (userA[i]) {
						case 1: // 상 
							yUserA--;
							break;
						case 2: // 우
							xUserA++;
							break;
						case 3: // 하
							yUserA++;
							break;
						case 4: // 좌
							xUserA--;
							break;
						}
						
						switch (userB[i]) {
						case 1: // 상 
							yUserB--;
							break;
						case 2: // 우 
							xUserB++;
							break;
						case 3: // 하 
							yUserB++;
							break;
						case 4: // 좌
							xUserB--;
							break;
						}
					}
					
					// 해당 시간에 사용자 A, B가 도달 가능한 BC 목록
					List<Integer> BCForUserA = new ArrayList<Integer>();
					List<Integer> BCForUserB = new ArrayList<Integer>();
					
					for (int j = 0; j < numA; j++) {
						int distanceA = Math.abs(xUserA - xBC[j]) + Math.abs(yUserA - yBC[j]);
						int distanceB = Math.abs(xUserB - xBC[j]) + Math.abs(yUserB - yBC[j]);
						
						if (distanceA <= cBC[j])
							BCForUserA.add(j);
						if (distanceB <= cBC[j])
							BCForUserB.add(j);
					}
					
					// 각 시간 별 최대값 구함 
					int maxValue = 0;
					
					if (BCForUserA.size() >= 1 && BCForUserB.size() >= 1) { // 둘 다 경우의 수가 1 이상이면 비교 필요				
						for (int caseA: BCForUserA) {
							for (int caseB: BCForUserB) {
								if (caseA == caseB) { // 같은 경우 절반씩 나눠가짐
									if (maxValue < 0.5 * (pBC[caseA] + pBC[caseB]))
										maxValue = (int) (0.5 * (pBC[caseA] + pBC[caseB]));
								}
								else { // 다른 경우 각자의 최대값 적용
									if (maxValue < pBC[caseA] + pBC[caseB])
										maxValue = pBC[caseA] + pBC[caseB];								
								}
							}						
						}
					}
					else { // 둘 중 한 쪽 이상이 size() == 0이면 한쪽만 계산
						if (BCForUserA.size() == 0 && BCForUserB.size() == 0) // 둘 다 0
							continue;
						else if (BCForUserA.size() == 0) { // B만 경우의 수가 있음
							for (int caseB: BCForUserB) {
								if (maxValue < pBC[caseB]) 
									maxValue = pBC[caseB];
							}
						}
						else if (BCForUserB.size() == 0) { // A만 경우의 수가 있음
							for (int caseA: BCForUserA) {
								if (maxValue < pBC[caseA]) 
									maxValue = pBC[caseA];
							}							
						}							
					}
					
					answer += maxValue;
				}
				
				writer.write(answer + System.lineSeparator());
				writer.flush();
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}