Submission #2072640


Source Code Expand

//Food Collector
#include<iostream>
#include<fstream>
#include<stdio.h>
#include<time.h>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<set>
#include<stack>
#include<cstdlib>
#include<algorithm>
#include<random>
#include<cassert>
using namespace std;
#define LL long long
#define INT_MIN -2147483648
#define INT_MAX 2147483647
#define LL_MIN -9223372036854775808
#define LL_MAX 9223372036854775807
#define ROOP() while(true)

int H,W,K;
int sx,sy;
bool mp[50][50];
int N;
pair<int,int> esa[50][50];
vector<pair<int,int> > ok_list;
vector<pair<int,int> > esa_list;
int dis[50][50][50][50] = {};
set<pair<int,int> > sumi;

//最短距離計算
void search(int sx, int sy, int x, int y, int c){
	if(mp[x-1][y] && dis[sx][sy][x-1][y]>c+1){
		dis[sx][sy][x-1][y] = c+1;
		search(sx,sy,x-1,y,c+1);
	}
	if(mp[x+1][y] && dis[sx][sy][x+1][y]>c+1){
		dis[sx][sy][x+1][y] = c+1;
		search(sx,sy,x+1,y,c+1);
	}
	if(mp[x][y-1] && dis[sx][sy][x][y-1]>c+1){
		dis[sx][sy][x][y-1] = c+1;
		search(sx,sy,x,y-1,c+1);
	}
	if(mp[x][y+1] && dis[sx][sy][x][y+1]>c+1){
		dis[sx][sy][x][y+1] = c+1;
		search(sx,sy,x,y+1,c+1);
	}
}

//最短距離逆探索・最適スコア計算
int tmp_cost[50][50];
void back(int nx, int ny, int gx, int gy, int c){
    //if(nx==22&&ny==4) cout << "Year!" << c;
	if(c<0) c=0;
    if(dis[gx][gy][nx-1][ny] == dis[gx][gy][nx][ny]-1 && 
	tmp_cost[nx-1][ny] < c+max(esa[nx-1][ny].first-esa[nx-1][ny].second*dis[gx][gy][nx-1][ny],0)){
		tmp_cost[nx-1][ny] = c+max(esa[nx-1][ny].first-esa[nx-1][ny].second*dis[gx][gy][nx-1][ny],0);
		back(nx-1,ny,gx,gy,c+max(esa[nx-1][ny].first-esa[nx-1][ny].second*dis[gx][gy][nx-1][ny],0));
	}
	if(dis[gx][gy][nx+1][ny] == dis[gx][gy][nx][ny]-1 && 
	tmp_cost[nx+1][ny] < c+max(esa[nx+1][ny].first-esa[nx+1][ny].second*dis[gx][gy][nx+1][ny],0)){
		tmp_cost[nx+1][ny] = c+max(esa[nx+1][ny].first-esa[nx+1][ny].second*dis[gx][gy][nx+1][ny],0);
		back(nx+1,ny,gx,gy,c+max(esa[nx+1][ny].first-esa[nx+1][ny].second*dis[gx][gy][nx+1][ny],0));
	}
	if(dis[gx][gy][nx][ny-1] == dis[gx][gy][nx][ny]-1 && 
	tmp_cost[nx][ny-1] < c+max(esa[nx][ny-1].first-esa[nx][ny-1].second*dis[gx][gy][nx][ny-1],0)){
		tmp_cost[nx][ny-1] = c+max(esa[nx][ny-1].first-esa[nx][ny-1].second*dis[gx][gy][nx][ny-1],0);
		back(nx,ny-1,gx,gy,c+max(esa[nx][ny-1].first-esa[nx][ny-1].second*dis[gx][gy][nx][ny-1],0));
	}
	if(dis[gx][gy][nx][ny+1] == dis[gx][gy][nx][ny]-1 && 
	tmp_cost[nx][ny+1] < c+max(esa[nx][ny+1].first-esa[nx][ny+1].second*dis[gx][gy][nx][ny+1],0)){
		tmp_cost[nx][ny+1] = c+max(esa[nx][ny+1].first-esa[nx][ny+1].second*dis[gx][gy][nx][ny+1],0);
		back(nx,ny+1,gx,gy,c+max(esa[nx][ny+1].first-esa[nx][ny+1].second*dis[gx][gy][nx][ny+1],0));
	}
}

int s_time;
int nokori;
int main(){
	//データ入力ここから↓
	
	cin >> H >> W >> K;
	s_time = clock();
	cin >> sy >> sx;
	nokori = K;
	sx--;
	sy--;
	
	for(int i=0; i<H; i++){
		string s;
		cin >> s;
		for(int j=0; j<W; j++){
			if(s[j]=='.'){
				mp[j][i]=true;
				ok_list.push_back(make_pair(j,i));
			}
			else mp[j][i]=false;

			for(int k=0; k<H; k++){
				for(int l=0; l<W; l++){
					dis[j][i][l][k] = INT_MAX;
				}
			}
			dis[j][i][j][i] = 0;
		}
	}

	for(int i=0; i<H; i++){
		for(int j=0; j<W; j++){
			esa[j][i] = make_pair(0,0);
		}
	}

	cin >> N;
	for(int i=0; i<N; i++){
		int x,y,F,D;
		cin >> y >> x >> F >> D;
		esa[x-1][y-1].first = F;
		esa[x-1][y-1].second = D;
		esa_list.push_back(make_pair(x-1,y-1));
	}

	//データ入力ここまで↑

	//メイン処理ここから↓
	int nx = sx;
	int	ny = sy;
	while(nokori>0){
		//[1] 最短距離計算
		// if(sumi.count(make_pair(nx,ny)) <= 0){
		// 	search(nx, ny, nx, ny, 0);
		// 	sumi.insert(make_pair(nx,ny));
		// }
        search(nx, ny, nx, ny, 0);

        // for(int i=0; i<50; i++){
		// 	for(int j=0; j<50; j++){
		// 		if(dis[nx][ny][j][i]==INT_MAX) cout << "# ";
		// 		else cout << dis[nx][ny][j][i] << " ";
		// 	}
		// 	cout << endl;
		// }

		//[2] 優先度の計算・行き先の決定
		int max_real = INT_MIN;
		int i_m = -1;
		for(int i=0; i<esa_list.size(); i++){
			if(dis[nx][ny][esa_list.at(i).first][esa_list.at(i).second] <= nokori){
				int real = esa[esa_list.at(i).first][esa_list.at(i).second].first
					- esa[esa_list.at(i).first][esa_list.at(i).second].second * dis[nx][ny][esa_list.at(i).first][esa_list.at(i).second];
				if(real>max_real){
					max_real = real;
					i_m = i;
				}
				if(real==max_real && dis[nx][ny][esa_list.at(i).first][esa_list.at(i).second]<dis[nx][ny][esa_list.at(i_m).first][esa_list.at(i_m).second]){
					max_real = real;
					i_m = i;
				}
			}
			
		}
		if(i_m == -1){
			for(int i=0; i<nokori; i++) cout << "U";
			return 0;
		}
        //cout << esa_list.at(i_m).first << " " << esa_list.at(i_m).second;


		//[3] 最適経路の計算
		for(int i=0; i<50; i++){
			for(int j=0; j<50; j++){
				tmp_cost[j][i] = -1;
			}
		}
        tmp_cost[esa_list.at(i_m).first][esa_list.at(i_m).second] = 0;
		back(esa_list.at(i_m).first, esa_list.at(i_m).second, nx, ny, 0);

		// for(int i=0; i<50; i++){
		// 	for(int j=0; j<50; j++){
		// 		cout << tmp_cost[j][i] << " ";
		// 	}
		// 	cout << endl;
		// }

		//[4] 移動処理
		int mx = nx;
		int my = ny;
        int kaisu = dis[nx][ny][esa_list.at(i_m).first][esa_list.at(i_m).second];
		for(int i=0; i<kaisu; i++){
			int tmp = -1;
			string s = "-";
			if(dis[mx][my][nx-1][ny] == dis[mx][my][nx][ny]+1 && tmp_cost[nx-1][ny] > tmp){
				tmp = tmp_cost[nx-1][ny];
				s = "L";
			}
			if(dis[mx][my][nx+1][ny] == dis[mx][my][nx][ny]+1 && tmp_cost[nx+1][ny] > tmp){
				tmp = tmp_cost[nx+1][ny];
				s = "R";
			}
			if(dis[mx][my][nx][ny-1] == dis[mx][my][nx][ny]+1 && tmp_cost[nx][ny-1] > tmp){
				tmp = tmp_cost[nx][ny-1];
				s = "U";
			}
			if(dis[mx][my][nx][ny+1] == dis[mx][my][nx][ny]+1 && tmp_cost[nx][ny+1] > tmp){
				tmp = tmp_cost[nx][ny+1];
				s = "D";
			}
			cout << s;
			if(s=="L") nx--;
			if(s=="R") nx++;
			if(s=="U") ny--;
			if(s=="D") ny++;
			if(esa[nx][ny].first>0){
				esa[nx][ny] = make_pair(0,0);
			}
			nokori--;
		}
        esa_list.clear();
        for(int i=0; i<H; i++){
            for(int j=0; j<W; j++){
                if(esa[j][i].first > 0) esa[j][i].first -= esa[j][i].second * kaisu;
                if(esa[j][i].first < 0) esa[j][i].first = 0;
                if(esa[j][i].first > 0) esa_list.push_back(make_pair(j,i));
            }
        }
		//int kara;
        //cin >> kara;
        //cout << nokori << " " << nx << " " << ny << endl;
	}
	//メイン処理ここまで↑

	cout << endl;
 
	//cout << (clock()-s_time)/CLOCKS_PER_SEC << endl;

	return 0;
}

Submission Info

Submission Time
Task B - Food Collector
User Pro_ktmr
Language C++14 (GCC 5.4.1)
Score 12712
Code Size 6850 Byte
Status AC
Exec Time 107 ms
Memory 24832 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 1219 / 20000 1452 / 20000 1256 / 20000 805 / 20000 1426 / 20000 1701 / 20000 1274 / 20000 1218 / 20000 816 / 20000 1545 / 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 58 ms 24704 KB
subtask_01_02.txt AC 107 ms 24832 KB
subtask_01_03.txt AC 103 ms 24832 KB
subtask_01_04.txt AC 90 ms 24832 KB
subtask_01_05.txt AC 81 ms 24832 KB
subtask_01_06.txt AC 92 ms 24832 KB
subtask_01_07.txt AC 97 ms 24832 KB
subtask_01_08.txt AC 70 ms 24832 KB
subtask_01_09.txt AC 64 ms 24704 KB
subtask_01_10.txt AC 101 ms 24832 KB