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