[SWEA 5644] 무선 충전

SW Expert Academy :: SWEA :: 5644 :: 무선 충전

출처 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo

#include <iostream>

#include <vector>

#include <memory.h>

#include <algorithm>

using namespace std;

struct BC {

int x, y, c, p, n;

};

int M, N, ans;

int user[2][101];

int dir[5][2] = { {0,0},{0,-1},{1,0},{0,1},{-1,0} };

vector <vector<vector<pair<int, int>>>> map;

inline bool check(int x, int y, BC bc) { return bc.c >= ((abs(bc.x-x) + abs(bc.y-y))) ? true : false; }

inline bool compare(const pair<int, int>&a, const pair<int, int>&b) { return a.first > b.first; }

void bcinput(BC bc) {

for (int i = (bc.y - bc.c); i <= (bc.y + bc.c); i++) {

for (int j = (bc.x - bc.c); j <= (bc.x + bc.c); j++) {

if (i >= 1 && i <= 10 && j >= 1 && j <= 10 && check(j, i, bc)) {

map[i][j].push_back(make_pair(bc.p,bc.n));

}

}

}

}

void input() {

cin >> M >> N; ans = 0; map.assign(11, vector<vector<pair<int, int>>>(11));

BC bc;

for (int i = 0; i < 2; i++) {

for (int j = 1; j <= M; j++) {

cin >> user[i][j];

}

}

for (int i = 0; i < N; i++) {

cin >> bc.x >> bc.y >> bc.c >> bc.p; bc.n = i;

bcinput(bc);

}

for (int i = 1; i <= 10; i++) {

for (int j = 1; j <= 10; j++) {

if (map[i][j].size()>0) {

sort(map[i][j].begin(), map[i][j].end(), compare);

}

}

}

}

int main() {

int T; cin >> T;

for (int tc = 1; tc <= T; tc++) {

input();

int u1[2] = { 1,1 }; int u2[2] = { 10,10 };

for (int t = 0; t <= M; t++) {

u1[0] += dir[user[0][t]][0];u1[1] += dir[user[0][t]][1];

u2[0] += dir[user[1][t]][0];u2[1] += dir[user[1][t]][1];

if (u1[0] == u2[0] && u1[1] == u2[1]) {

if (map[u1[1]][u1[0]].size() > 0) {

if(map[u1[1]][u1[0]].size()>1)ans += (map[u1[1]][u1[0]][0].first + map[u1[1]][u1[0]][1].first);

else ans += map[u1[1]][u1[0]][0].first;

}

}

else if (map[u1[1]][u1[0]].size() > 0 && map[u2[1]][u2[0]].size() > 0) {

int tmp1, tmp2; bool c1[8], c2[8]; memset(c1, 0, sizeof(c1));memset(c2, 0, sizeof(c2));

tmp1 = map[u1[1]][u1[0]][0].first; c1[map[u1[1]][u1[0]][0].second] = true;

if (c1[map[u2[1]][u2[0]][0].second]) {

if (map[u2[1]][u2[0]].size() > 1) tmp1 += map[u2[1]][u2[0]][1].first;

}

else tmp1 += map[u2[1]][u2[0]][0].first;

tmp2 = map[u2[1]][u2[0]][0].first; c2[map[u2[1]][u2[0]][0].second] = true;

if (c2[map[u1[1]][u1[0]][0].second]) {

if (map[u1[1]][u1[0]].size() > 1) tmp2 += map[u1[1]][u1[0]][1].first;

}

else tmp2 += map[u1[1]][u1[0]][0].first;

ans += max(tmp1, tmp2);

}

else {

if (map[u1[1]][u1[0]].size() > 0) {

ans += map[u1[1]][u1[0]][0].first;

}

else if (map[u2[1]][u2[0]].size() > 0) {

ans += map[u2[1]][u2[0]][0].first;

}

}

}

cout << "#" << tc << " " << ans << endl;

}

return 0;

}