Submission #1350800


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 1.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);
	stats[0].push(STATE(0,-1, make_pair(sr, sc), vector<int>(N), 0));

	int turn;

	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;
				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;
				}

				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++;
		}
	}

	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 0
Code Size 5996 Byte
Status MLE
Exec Time 1279 ms
Memory 2094592 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 0 / 20000 0 / 20000 0 / 20000 0 / 20000 0 / 20000 0 / 20000 0 / 20000
Status
MLE × 1
MLE × 1
MLE × 1
MLE × 1
MLE × 1
MLE × 1
MLE × 1
MLE × 1
MLE × 1
MLE × 1
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 1216 ms 1711744 KB
subtask_01_02.txt MLE 1279 ms -2073732 KB
subtask_01_03.txt MLE 1261 ms 2079872 KB
subtask_01_04.txt MLE 1245 ms 1744848 KB
subtask_01_05.txt MLE 1246 ms 2031088 KB
subtask_01_06.txt MLE 1264 ms -2067584 KB
subtask_01_07.txt MLE 1260 ms 2094592 KB
subtask_01_08.txt MLE 1242 ms 1944352 KB
subtask_01_09.txt MLE 1237 ms 1779048 KB
subtask_01_10.txt MLE 1255 ms -2089344 KB