Submission #369490

#	Time	Username	Problem	Language	Result	Execution time	Memory
369490		YJU	Robots (APIO13_robots)	C++14	60 / 100	1592 ms	132964 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;
	node(ll _a,ll _b,ll _c):Dis(_a),x(_b),y(_c){};
	//state :at (x,y)
	//  3
	//  |
	//4-0-2
	//  |
	//  1
	void out(){
		cout<<"Dis("<<Dis<<"),x("<<x<<"),y("<<y<<")\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];
//dp[x][y][l][r] represents minimum times of operation to make robot[l,r] stay at grid[x][y]
pll nxt_state[N][N][5];
 
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');
}

void build(ll x,ll y,ll dir){
	nxt_state[x][y][dir]=mp(-1,-1);
	if(invalid(x+dx[dir],y+dy[dir])){
		nxt_state[x][y][dir]=mp(x,y);
		return ;
	}
	ll nx=x+dx[dir],ny=y+dy[dir],ndir=dir;
	if(grid[nx][ny]=='A'){
		ndir=(dir+1==5?1:dir+1);
	}else if(grid[nx][ny]=='C'){
		ndir=(dir-1==0?4:dir-1);
	}
	if(nxt_state[nx][ny][ndir]==mp(0,0)){build(nx,ny,ndir);}
	nxt_state[x][y][dir]=nxt_state[nx][ny][ndir];
}
 
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)REP1(dir,4){
		if(nxt_state[i][j][dir]==mp(0,0)){
			build(i,j,dir);
		}
	}
	//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){
				dis[i][j]=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]=dp[i][j][l][r];
				if(dis[i][j]<INF){
					pq.push(node(dis[i][j],i,j));
				}
				//
			}
			//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])continue;
				//nd.out();
				//stand at (nd.x,nd.y)
				dp[nd.x][nd.y][l][r]=nd.Dis;
				REP1(dir,4){
					pll nxt=nxt_state[nd.x][nd.y][dir];
					if(nxt==mp(-1,-1))continue;
					ll nx=nxt.X,ny=nxt.Y;
					if(dis[nx][ny]>nd.Dis+1){
						dis[nx][ny]=nd.Dis+1;
						pq.push(node(nd.Dis+1,nx,ny));
					}
				}
			}
		}
	}
	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