Submission #1402603


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 time < right.time;
	}
};
 
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,K, 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 < 0)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 4154
Code Size 6480 Byte
Status AC
Exec Time 9130 ms
Memory 99840 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 257 / 20000 779 / 20000 376 / 20000 124 / 20000 627 / 20000 685 / 20000 555 / 20000 376 / 20000 278 / 20000 97 / 20000
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 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 AC 9068 ms 64128 KB
subtask_01_02.txt AC 9130 ms 99840 KB
subtask_01_03.txt AC 9100 ms 73344 KB
subtask_01_04.txt AC 9047 ms 35456 KB
subtask_01_05.txt AC 9078 ms 65152 KB
subtask_01_06.txt AC 9107 ms 85504 KB
subtask_01_07.txt AC 9097 ms 77188 KB
subtask_01_08.txt AC 9067 ms 55552 KB
subtask_01_09.txt AC 9039 ms 38656 KB
subtask_01_10.txt AC 9094 ms 82304 KB