Submission #1351141
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;
//return score < right.score;
}
};
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);
stats[0].push(STATE(0, -1, make_pair(sr, sc), vector<int>(N), 0));
//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;
for (int k = 0; k < 1500;k++) {
//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());
STATE nowState = stats[turn].top();
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;
}
if (stats[turn + 1].size() > 1000)continue;
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(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 << 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 |
3804 |
Code Size |
6678 Byte |
Status |
MLE |
Exec Time |
9529 ms |
Memory |
2051328 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 |
0 / 20000 |
0 / 20000 |
0 / 20000 |
1098 / 20000 |
0 / 20000 |
0 / 20000 |
0 / 20000 |
1539 / 20000 |
1167 / 20000 |
0 / 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 |
MLE |
9255 ms |
1275424 KB |
subtask_01_02.txt |
MLE |
9529 ms |
-1127052 KB |
subtask_01_03.txt |
MLE |
9329 ms |
1685248 KB |
subtask_01_04.txt |
AC |
9115 ms |
379136 KB |
subtask_01_05.txt |
MLE |
9276 ms |
1362816 KB |
subtask_01_06.txt |
MLE |
9426 ms |
-1776256 KB |
subtask_01_07.txt |
MLE |
9346 ms |
1745664 KB |
subtask_01_08.txt |
AC |
9209 ms |
896512 KB |
subtask_01_09.txt |
AC |
9121 ms |
428416 KB |
subtask_01_10.txt |
MLE |
9376 ms |
2051328 KB |