Submission #2071424
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))
using ll = long long;
using P = pair<int, int>;
using namespace std;
template<class T> void vin(vector<T>& v, int n) {
v.resize(n);
for (int i = 0; i < n; ++i) {
cin >> v[i];
}
}
int H, W, K, N, sr, sc;
string board[51];
int fr[2501], fc[2501], f[2501], d[2501];
int dc[] = { 1, 0, -1, 0 };
int dr[] = { 0, 1, 0, -1 };
string dir[] = { "R", "D", "L", "U", "-" };
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
cin >> H >> W >> K >> sr >> sc;
sr--;
sc--;
rep(i, H) cin >> board[i];
cin >> N;
int turn = 0;
rep(i, N) {
cin >> fr[i] >> fc[i] >> f[i] >> d[i];
fr[i]--;
fc[i]--;
}
bitset<2501> used;
P pos = make_pair(sr, sc);
string ans = "";
while (turn < K) {
bool hit = false;
queue<P> que;
que.push(pos);
string mp[2501];
mp[pos.first*50+pos.second] = "";
bitset<2501> visited;
visited[pos.first*50+pos.second] = true;
while (que.size()) {
P p = que.front();
que.pop();
rep(i, 4) {
int nr = p.first + dr[i], nc = p.second + dc[i];
if (nr < 0 or nr >= H or nc < 0 or nc >= W or board[nr][nc] == '#' or visited[nr*50+nc] == true) continue;
mp[nr*50+nc] = mp[p.first*50+p.second] + dir[i];
visited[nr*50+nc] = true;
que.push(make_pair(nr, nc));
}
}
int dist = 1e8;
ll best = 0;
int idx = -1;
rep(i, N) {
if (used[i]) continue;
if (mp[fr[i]*50+fc[i]].size() > 0 and mp[fr[i]*50+fc[i]].size() + turn <= K and dist >= mp[fr[i]*50+fc[i]].size() and (ll)f[i] - (ll)(mp[fr[i]*50+fc[i]].size() + turn)*d[i] > 0LL) {
if (dist == mp[fr[i]*50+fc[i]].size() and best > (ll)f[i] - (ll)(mp[fr[i]*50+fc[i]].size() + turn)*d[i]) continue;
dist = mp[fr[i]*50+fc[i]].size();
best = (ll)f[i] - (ll)(mp[fr[i]*50+fc[i]].size() + turn)*d[i];
idx = i;
hit = true;
}
}
if (!hit) {
break;
}
ans += mp[fr[idx]*50+fc[idx]];
turn = ans.size();
pos = P(fr[idx], fc[idx]);
used[idx]=true;
}
int sz = ans.size();
for (int i = sz; i<K; ++i) {
ans += "-";
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Food Collector |
User |
dsytk7 |
Language |
C++14 (GCC 5.4.1) |
Score |
17998 |
Code Size |
2613 Byte |
Status |
AC |
Exec Time |
92 ms |
Memory |
512 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 |
1680 / 20000 |
2446 / 20000 |
1860 / 20000 |
1079 / 20000 |
1921 / 20000 |
2318 / 20000 |
1934 / 20000 |
1478 / 20000 |
1141 / 20000 |
2141 / 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 |
47 ms |
384 KB |
subtask_01_02.txt |
AC |
92 ms |
512 KB |
subtask_01_03.txt |
AC |
72 ms |
512 KB |
subtask_01_04.txt |
AC |
35 ms |
512 KB |
subtask_01_05.txt |
AC |
58 ms |
512 KB |
subtask_01_06.txt |
AC |
79 ms |
504 KB |
subtask_01_07.txt |
AC |
70 ms |
512 KB |
subtask_01_08.txt |
AC |
49 ms |
508 KB |
subtask_01_09.txt |
AC |
30 ms |
384 KB |
subtask_01_10.txt |
AC |
66 ms |
504 KB |