Submission #369476

#	Time	Username	Problem	Language	Result	Execution time	Memory
369476		YJU	Robots (APIO13_robots)	C++14	60 / 100	1591 ms	137316 KiB

robots

#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,dir;
	node(ll _a,ll _b,ll _c,ll _d):Dis(_a),x(_b),y(_c),dir(_d){};
	//state :at (x,y) dir(direction) 
	//  3
	//  |
	//4-0-2
	//  |
	//  1
	void out(){
		cout<<"Dis("<<Dis<<"),x("<<x<<"),y("<<y<<"),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][5],nxtx[N][N][5],nxty[N][N][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;
string grid[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)cin>>grid[i],grid[i]="x"+grid[i];
	//input end
	//prepare
	REP1(i,R)REP1(j,C){
		nxtx[i][j][3]=(invalid(i+dx[3],j)||grid[i+dx[3]][j]=='A'||grid[i+dx[3]][j]=='C'?i+dx[3]:nxtx[i+dx[3]][j][3]);
		nxty[i][j][4]=(invalid(i,j+dy[4])||grid[i][j+dy[4]]=='A'||grid[i][j+dy[4]]=='C'?j+dy[4]:nxty[i][j+dy[4]][4]);
	}
	for(int i=R;i>=1;i--)for(int j=C;j>=1;j--){
		nxtx[i][j][1]=(invalid(i+dx[1],j)||grid[i+dx[1]][j]=='A'||grid[i+dx[1]][j]=='C'?i+dx[1]:nxtx[i+dx[1]][j][1]);
		nxty[i][j][2]=(invalid(i,j+dy[2])||grid[i][j+dy[2]]=='A'||grid[i][j+dy[2]]=='C'?j+dy[2]:nxty[i][j+dy[2]][2]);
		
		nxtx[i][j][2]=nxtx[i][j][4]=i;
		nxty[i][j][1]=nxty[i][j][3]=j;
	}
	
	//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(dir,5)dis[i][j][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]=dp[i][j][l][r];
				if(dis[i][j][0]<INF){
					pq.push(node(dis[i][j][0],i,j,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.dir])continue;
				//nd.out();
				if(1){
					//have turned
					if(nd.dir==0){
						//stand at (nd.x,nd.y)
						dp[nd.x][nd.y][l][r]=nd.Dis;
						REP1(dir,4){
							ll nx=nxtx[nd.x][nd.y][dir],ny=nxty[nd.x][nd.y][dir];
							if(invalid(nx,ny)){
								nx-=dx[dir],ny-=dy[dir];
								if(dis[nx][ny][0]>nd.Dis+1){
									dis[nx][ny][0]=nd.Dis+1;
									pq.push(node(nd.Dis+1,nx,ny,0));
								}
							}else{
								ll ndir;
								if(grid[nx][ny]=='A'){
									ndir=(dir+1==5?1:dir+1);
								}else{
									ndir=(dir-1==0?4:dir-1);
								}
								if(dis[nx][ny][ndir]>nd.Dis+1){
									dis[nx][ny][ndir]=nd.Dis+1;
									pq.push(node(nd.Dis+1,nx,ny,ndir));
								}
							}
						}
					}else{
						//moving on or stop (cost = 0)
						ll nx=nxtx[nd.x][nd.y][nd.dir],ny=nxty[nd.x][nd.y][nd.dir];
						if(invalid(nx,ny)){
							nx-=dx[nd.dir],ny-=dy[nd.dir];
							if(dis[nx][ny][0]>nd.Dis){
								dis[nx][ny][0]=nd.Dis;
								pq.push(node(nd.Dis,nx,ny,0));
							}
						}else{
							ll ndir;
							if(grid[nx][ny]=='A'){
								ndir=(nd.dir+1==5?1:nd.dir+1);
							}else{
								ndir=(nd.dir-1==0?4:nd.dir-1);
							}
							if(dis[nx][ny][ndir]>nd.Dis){
								dis[nx][ny][ndir]=nd.Dis;
								pq.push(node(nd.Dis,nx,ny,ndir));
							}
						}
					}
				}
			}
		}
	}
	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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40