Submission #1350889
Source Code Expand
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <chrono>
#include <queue>
#include <functional>
using namespace std;
//タイマー
class Timer {
chrono::high_resolution_clock::time_point start, end;
double limit;
public:
Timer() {
start = chrono::high_resolution_clock::now();
}
Timer(double l) {
start = chrono::high_resolution_clock::now();
limit = l;
}
double getTime() {
end = chrono::high_resolution_clock::now();
return chrono::duration<double>(end - start).count();
}
bool Over() {
if (getTime() > limit) {
return true;
}
return false;
}
void setLimit(double l) {
limit = l;
}
void setStart() { start = chrono::high_resolution_clock::now(); }
};
#define SIZE 50
#define LIMIT 9.0
#define INF 1e7
int H, W, K, sr, sc;
int N;
vector<vector<int>>DIST[SIZE][SIZE];
vector<vector<int>>status;
vector<vector<int>>cost;
int h[] = { 0,1,0,-1 };
int v[] = { -1,0,1,0 };
vector<vector<int>>MAP;
bool range_over(pair<int, int>pos) {
if (pos.first < 0 || pos.first >= H || pos.second < 0 || pos.second >= W)return true;
return false;
}
void dijkstra(pair<int,int> s) {
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
status[i][j] = 0;
cost[i][j] = INF;
}
}
cost[s.first][s.second] = 0;
status[s.first][s.second] = 1;
priority_queue<pair<int, pair<int,int>>, vector<pair<int, pair<int,int>>>, greater<pair<int, pair<int,int>>>>U;
U.push(make_pair(cost[s.first][s.second], s));
while (!U.empty()) {
//探索が終わってない中でコスト最小の点
pair<int,int> u = U.top().second; U.pop();
if (status[u.first][u.second] == -1) continue;
status[u.first][u.second] = -1;
//コスト最少の点を探る
for (int i = 0; i < 4; i++) {
pair<int, int>nu;
nu.first = u.first + v[i];
nu.second = u.second + h[i];
if (range_over(pair<int, int>(nu.first, nu.second)))continue;
if (MAP[nu.first][nu.second])continue;
if (status[nu.first][nu.second] != -1) {
if (cost[nu.first][nu.second] > cost[u.first][u.second] + 1) {
cost[nu.first][nu.second] = cost[u.first][u.second] + 1;
status[nu.first][nu.second] = 1;
U.push(make_pair(cost[nu.first][nu.second], pair<int, int>(nu.first, nu.second)));
}
}
}
}
}
string dir[] = { "D","L","U","R" };
string pathfind(int r, int c, int r2, int c2) {
string path = "";
while (r != r2 || c != c2) {
for (int i = 0; i < 4; i++) {
int nr = r2 + v[i];
int nc = c2 + h[i];
if (range_over(pair<int, int>(nr, nc)))continue;
if (MAP[nr][nc])continue;
if (DIST[r][c][nr][nc] == DIST[r][c][r2][c2] - 1) {
path += dir[i];
r2 = nr;
c2 = nc;
break;
}
}
}
return path;
}
struct FOOD{
int r, c;
int F, D;
FOOD() {}
FOOD(int r_, int c_, int F_, int D_) {
r = r_, c = c_, F = F_, D = D_;
}
};
vector<FOOD>foods;
struct STATE {
int score;
int time;
pair<int, int>pos;
vector<int>order;
int loss;
STATE(int score_, int time_, pair<int, int>pos_, vector<int>order_, int loss_) {
score = score_, time = time_, pos = pos_, loss = loss_;
order = order_;
}
bool operator<(const STATE&right) const {
return loss < right.loss;
}
};
vector<int>next_order(vector<int>vec, int j, int turn) {
vec[j] = turn;
return vec;
}
vector<int> solve(){
Timer tmr(LIMIT);
vector<int>res(N);
int maxscore = 0;
int width = 1;
//vector<priority_queue<STATE>>stats(SIZE*SIZE);
vector<vector<STATE>>stats(SIZE*SIZE);
stats[0].push_back(STATE(0,-1, make_pair(sr, sc), vector<int>(N), 0));
int max_turn = 0;
int turn;
int cnt = 0;
while (!tmr.Over()) {
turn = 0;
while (!tmr.Over()) {
if (turn && stats[turn].empty())break;
for (int i = 0; i < width; i++) {
if (stats[turn].empty())break;
sort(stats[turn].begin(), stats[turn].end());
if (stats[turn].size() > 10*2500/(max_turn+1)) {
for (int k = stats[turn].size() - 1; k >= 10 * 2500 / (max_turn + 1); k--)stats[turn].erase(stats[turn].begin() + k);
}
STATE nowState = stats[turn][0];
stats[turn].erase(stats[turn].begin());
//stats[turn].pop();
if (nowState.score > maxscore) {
maxscore = nowState.score;
res = nowState.order;
}
int sumD = 0;
for (int j = 0; j < N; j++) {
if (nowState.order[j])continue;
sumD += foods[j].D;
}
for (int j = 0; j < N; j++) {
FOOD food = foods[j];
int dist = DIST[nowState.pos.first][nowState.pos.second][food.r][food.c];
int time = nowState.time + dist;
int score = food.F - food.D * time;
int loss = (sumD - food.D) * time;
if (time > K)continue;
if (score <= 0)continue;
if (nowState.order[j])continue;
stats[turn + 1].push_back(STATE(nowState.score + score, time, pair<int, int>(food.r, food.c), next_order(nowState.order, j, turn + 1), loss));
}
}
turn++;
max_turn = max(max_turn, turn);
}
cnt++;
}
cerr << cnt << endl;
cerr << maxscore << endl;
return res;
}
int main()
{
cin >> H >> W >> K;
cin >> sr >> sc;
sr--; sc--;
MAP.resize(H);
for (int i = 0; i < H; i++) {
MAP[i].resize(W);
for (int j = 0; j < W; j++) {
char c; cin >> c;
if (c == '#')MAP[i][j] = 1;
}
}
status.resize(SIZE, vector<int>(SIZE));
cost.resize(SIZE, vector<int>(SIZE));
dijkstra(pair<int, int>(sr, sc));
DIST[sr][sc] = cost;
cin >> N;
foods.resize(N);
for (int i = 0; i < N; i++) {
int r, c, F, D;
cin >> r >> c >> F >> D;
r--; c--;
foods[i] = FOOD(r, c, F, D);
dijkstra(pair<int,int>(r,c));
DIST[r][c] = cost;
}
vector<int>order = solve();
vector<pair<int,int>>path;
path.push_back(make_pair(0, N));
for (int i = 0; i < N; i++) {
if (order[i])path.push_back(make_pair(order[i],i));
}
sort(path.begin(), path.end());
foods.push_back(FOOD(sr,sc,0,0));
string ans="";
for (int i = path.size() - 2; i >= 0; i--) {
int p1 = path[i].second;
int p2 = path[i + 1].second;
int r = foods[p1].r;
int c = foods[p1].c;
int r2 = foods[p2].r;
int c2 = foods[p2].c;
ans += pathfind(r, c, r2, c2);
}
reverse(ans.begin(),ans.end());
ans += string(K - ans.size(),'-');
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Food Collector |
User |
kurenai3110 |
Language |
C++14 (GCC 5.4.1) |
Score |
18200 |
Code Size |
6430 Byte |
Status |
AC |
Exec Time |
9146 ms |
Memory |
390264 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 |
1731 / 20000 |
2397 / 20000 |
1903 / 20000 |
1142 / 20000 |
1979 / 20000 |
2319 / 20000 |
1899 / 20000 |
1562 / 20000 |
1207 / 20000 |
2061 / 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 |
9075 ms |
201728 KB |
subtask_01_02.txt |
AC |
9146 ms |
390264 KB |
subtask_01_03.txt |
AC |
9109 ms |
250172 KB |
subtask_01_04.txt |
AC |
9049 ms |
61188 KB |
subtask_01_05.txt |
AC |
9085 ms |
210960 KB |
subtask_01_06.txt |
AC |
9120 ms |
325316 KB |
subtask_01_07.txt |
AC |
9107 ms |
260620 KB |
subtask_01_08.txt |
AC |
9072 ms |
150144 KB |
subtask_01_09.txt |
AC |
9042 ms |
69252 KB |
subtask_01_10.txt |
AC |
9106 ms |
289292 KB |