Submission #2078748
Source Code Expand
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <functional>
using namespace std;
struct POINT {
int x, y;
POINT(int x=0,int y=0):x(x),y(y){}
POINT operator+(POINT r) {
return POINT(x + r.x, y + r.y);
}
bool operator<(const POINT& r)const {
return x + y < r.x + r.y;
}
bool operator==(POINT r) {
return x == r.x && y == r.y;
}
bool operator!=(POINT r) {
return x != r.x || y != r.y;
}
};
POINT DIR[4];
char mov[5];
struct FOOD {
POINT p;
int F, D;
int id;
FOOD(POINT p=POINT(), int F=0, int D=0, int id = -1):p(p),F(F),D(D),id(id){}
bool operator<(const FOOD& r)const {
return p < r.p;
}
};
#define INF 1e9
class Solver {
int H, W, K;
POINT sp;
int N;
vector<FOOD>food;
vector<string>GRIDs;
vector<vector<int>>GRID;
vector<char>used;
vector<int>ans;
vector<vector<int>>status, cost;
public:
void INPUT() {
cin >> H >> W >> K;
cin >> sp.x >> sp.y;
sp.x--; sp.y--;
GRIDs.resize(H);
for (int i = 0; i < H; i++)cin >> GRIDs[i];
cin >> N;
food.resize(N);
for (int i = 0; i < N; i++) {
cin >> food[i].p.x >> food[i].p.y >> food[i].F >> food[i].D;
food[i].id = i;
food[i].p.x--; food[i].p.y--;
}
}
void INIT() {
DIR[0] = POINT(-1, 0);
DIR[1] = POINT(0, 1);
DIR[2] = POINT(1, 0);
DIR[3] = POINT(0, -1);
mov[1] = 'D';
mov[2] = 'L';
mov[3] = 'U';
mov[4] = 'R';
mov[0] = '-';
INPUT();
status.resize(H, vector<int>(W));
cost.resize(H, vector<int>(W));
GRID.resize(H, vector<int>(W));
used.resize(N);
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
char c = GRIDs[i][j];
if(c=='#')GRID[i][j] = 1;
}
}
}
void solve() {
POINT pos = sp;
int t = 0;
while (1) {
dijkstra(pos);
vector<pair<int, FOOD>>Kouho;
for (int i = 0; i < N; i++) {
if (used[i])continue;
POINT fp = food[i].p;
int score = max(0, food[i].F - food[i].D*(t + cost[fp.x][fp.y]));
if (score) {
Kouho.push_back(make_pair(score, food[i]));
}
}
if (Kouho.empty()) {
ans.resize(K);
break;
}
sort(Kouho.begin(), Kouho.end());
vector<int>ret = pathfind(pos, Kouho.back().second.p);
for (int i = 0; i < ret.size(); i++)ans.push_back(ret[i]);
pos = Kouho.back().second.p;
t += cost[pos.x][pos.y];
used[Kouho.back().second.id] = true;
}
}
void OUTPUT() {
for (int i = 0; i < K; i++)cout << mov[ans[i]];
cout << endl;
}
bool OVER(POINT p) {
return p.x < 0 || p.x >= H || p.y < 0 || p.y >= W;
}
void run() {
INIT();
solve();
OUTPUT();
}
void dijkstra(POINT s) {
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
status[i][j] = 0;
cost[i][j] = INF;
}
}
status[s.x][s.y] = 1;
cost[s.x][s.y] = 0;
priority_queue < pair<int, POINT>, vector<pair<int, POINT>>, greater<pair<int, POINT>>>Q;
Q.push(make_pair(cost[s.x][s.y], s));
while (Q.size()) {
POINT p = Q.top().second;Q.pop();
if (status[p.x][p.y] == -1)continue;
status[p.x][p.y] = -1;
for (int k = 0; k < 4; k++) {
POINT np = p + DIR[k];
if (OVER(np))continue;
if (status[np.x][np.y] == -1)continue;
if (GRID[np.x][np.y])continue;
if (cost[np.x][np.y] <= cost[p.x][p.y] + 1)continue;
cost[np.x][np.y] = cost[p.x][p.y] + 1;
status[np.x][np.y] = 1;
Q.push(make_pair(cost[np.x][np.y], np));
}
}
}
vector<int>pathfind(POINT from, POINT to) {
vector<int>ret;
while (from != to) {
for (int k = 0; k < 4; k++) {
POINT np = to + DIR[k];
if (OVER(np))continue;
if (cost[np.x][np.y] == cost[to.x][to.y] - 1) {
to = np;
ret.push_back(k+1);
break;
}
}
}
reverse(ret.begin(), ret.end());
return ret;
}
};
int main() {
Solver slv;
slv.run();
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Food Collector |
User |
kurenai3110 |
Language |
C++14 (Clang 3.8.0) |
Score |
5309 |
Code Size |
3984 Byte |
Status |
AC |
Exec Time |
25 ms |
Memory |
384 KB |
Judge Result
Set Name |
test_01 |
test_02 |
test_03 |
test_04 |
test_05 |
test_06 |
test_07 |
test_08 |
test_09 |
test_10 |
Score / Max Score |
629 / 20000 |
688 / 20000 |
338 / 20000 |
486 / 20000 |
424 / 20000 |
705 / 20000 |
337 / 20000 |
669 / 20000 |
379 / 20000 |
654 / 20000 |
Status |
|
|
|
|
|
|
|
|
|
|
Set Name |
Test Cases |
test_01 |
subtask_01_01.txt |
test_02 |
subtask_01_02.txt |
test_03 |
subtask_01_03.txt |
test_04 |
subtask_01_04.txt |
test_05 |
subtask_01_05.txt |
test_06 |
subtask_01_06.txt |
test_07 |
subtask_01_07.txt |
test_08 |
subtask_01_08.txt |
test_09 |
subtask_01_09.txt |
test_10 |
subtask_01_10.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask_01_01.txt |
AC |
15 ms |
384 KB |
subtask_01_02.txt |
AC |
25 ms |
384 KB |
subtask_01_03.txt |
AC |
19 ms |
384 KB |
subtask_01_04.txt |
AC |
13 ms |
384 KB |
subtask_01_05.txt |
AC |
17 ms |
384 KB |
subtask_01_06.txt |
AC |
21 ms |
384 KB |
subtask_01_07.txt |
AC |
19 ms |
384 KB |
subtask_01_08.txt |
AC |
16 ms |
384 KB |
subtask_01_09.txt |
AC |
10 ms |
384 KB |
subtask_01_10.txt |
AC |
18 ms |
384 KB |