oj.uz

답안 #369456

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
369456 2021-02-21T17:28:13 Z YJU 로봇 (APIO13_robots) C++14
30 / 100
 1500 ms 50912 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=5e2+5;
const ld pi=acos(-1);
const ll INF=(1LL<<29);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
 
struct node{
	ll Dis,x,y,ty,dir;
	node(ll _a,ll _b,ll _c,ll _d,ll _e):Dis(_a),x(_b),y(_c),ty(_d),dir(_e){};
	//state :at (x,y) ty(turn yet?0:1) dir(direction) 
	//  3
	//  |
	//4-0-2
	//  |
	//  1
	void out(){
		cout<<"Dis("<<Dis<<"),x("<<x<<"),y("<<y<<"),ty("<<ty<<"),dir("<<dir<<")\n";
	}
};
 
struct cmp{
	bool operator()(node A,node B){
		return A.Dis>B.Dis;
	}
};
 
priority_queue<node,vector<node>,cmp> pq;
 
 
ll dp[N][N][11][11],dis[N][N][2][5];
//dp[x][y][l][r] represents minimum times of operation to make robot[l,r] stay at grid[x][y]
 
ll dx[5]={0,1,0,-1,0},dy[5]={0,0,1,0,-1};
 
 
ll n,R,C;
char grid[N][N];
 
bool invalid(ll x,ll y){
	return !(0<x&&x<=R&&0<y&&y<=C&&grid[x][y]!='x');
}
 
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	//input
	cin>>n>>C>>R;
	REP1(i,R)REP1(j,C){
		//while((grid[i][j]=getchar())=='\n');
		cin>>grid[i][j];
	}
	//input end
	
	//len = r-l+1 for robot[l,r]
	for(int len=1;len<=n;len++){
		for(int l=1,r=l+len-1;l+len-1<=n;l++,r++){
			//merging robots to robot[l,r]
			REP1(i,R)REP1(j,C){
				REP(ty,2)REP(dir,5)dis[i][j][ty][dir]=INF;
				if(len==1){
					dp[i][j][l][r]=(grid[i][j]-'0'==l?0:INF);
				}else{
					dp[i][j][l][r]=INF;
					for(int cut=l;cut+1<=r;cut++){
						dp[i][j][l][r]=min(dp[i][j][l][r],dp[i][j][l][cut]+dp[i][j][cut+1][r]);
					}
				}
				//
				dis[i][j][0][0]=dp[i][j][l][r];
				if(dis[i][j][0][0]<INF){
					pq.push(node(dis[i][j][0][0],i,j,0,0));
				}
				//
			}
			//moving robots ( O(N*N*log(N*N) ) )
			while(SZ(pq)){
				node nd=pq.top();pq.pop();
				if(nd.Dis!=dis[nd.x][nd.y][nd.ty][nd.dir])continue;
				//nd.out();
				if(nd.ty==0){
					//have turned
					if(nd.dir==0){
						dp[nd.x][nd.y][l][r]=nd.Dis;
						//stand at (nd.x,nd.y)
						REP1(dir,4){
							//push to dir (cost = 1)
							if(dis[nd.x][nd.y][1][dir]>nd.Dis+1){
								dis[nd.x][nd.y][1][dir]=nd.Dis+1;
								pq.push(node(nd.Dis+1,nd.x,nd.y,1,dir));
							}
						}
					}else{
						//moving on or stop (cost = 0)
						if(invalid(nd.x+dx[nd.dir],nd.y+dy[nd.dir])){
							if(dis[nd.x][nd.y][0][0]>nd.Dis){
								dis[nd.x][nd.y][0][0]=nd.Dis;
								pq.push(node(nd.Dis,nd.x,nd.y,0,0));
							}
						}else{
							ll nx=nd.x+dx[nd.dir],ny=nd.y+dy[nd.dir];
							if(dis[nx][ny][1][nd.dir]>nd.Dis){
								dis[nx][ny][1][nd.dir]=nd.Dis;
								pq.push(node(nd.Dis,nx,ny,1,nd.dir));
							}
						}
					}
				}else if(nd.ty==1){
					if(nd.dir==0)continue;
					if(grid[nd.x][nd.y]=='A'){
						ll ndir=(nd.dir+1==5?1:nd.dir+1);
						if(dis[nd.x][nd.y][0][ndir]>nd.Dis){
							dis[nd.x][nd.y][0][ndir]=nd.Dis;
							pq.push(node(nd.Dis,nd.x,nd.y,0,ndir));
						}
					}else if(grid[nd.x][nd.y]=='C'){
						ll ndir=(nd.dir-1==0?4:nd.dir-1);
						if(dis[nd.x][nd.y][0][ndir]>nd.Dis){
							dis[nd.x][nd.y][0][ndir]=nd.Dis;
							pq.push(node(nd.Dis,nd.x,nd.y,0,ndir));
						}
					}else{
						if(dis[nd.x][nd.y][0][nd.dir]>nd.Dis){
							dis[nd.x][nd.y][0][nd.dir]=nd.Dis;
							pq.push(node(nd.Dis,nd.x,nd.y,0,nd.dir));
						}
					}
				}
			}
			//update after moving
			
			//cout<<"robot["<<l<<","<<r<<"]\n";
		}
	}
	ll ans=INF;
	REP1(i,R)REP1(j,C){
		ans=min(ans,dp[i][j][1][n]);
	}
	cout<<(ans==INF?-1:ans)<<"\n";
	return 0;
}
/*
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
*/

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1135 ms 50912 KB Output is correct
12 Correct 43 ms 48108 KB Output is correct
13 Correct 533 ms 49260 KB Output is correct
14 Execution timed out 1565 ms 49636 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1135 ms 50912 KB Output is correct
12 Correct 43 ms 48108 KB Output is correct
13 Correct 533 ms 49260 KB Output is correct
14 Execution timed out 1565 ms 49636 KB Time limit exceeded
15 Halted 0 ms 0 KB -