oj.uz

Submission #369476

# Submission time Handle Problem Language Result Execution time Memory
369476 2021-02-21T18:18:44 Z YJU Robots (APIO13_robots) C++14
60 / 100
 1500 ms 137316 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,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.0 / 10.0

# Verdict Execution time Memory 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 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory 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 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 1 ms 620 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory 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 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 314 ms 52840 KB Output is correct
12 Correct 35 ms 52076 KB Output is correct
13 Correct 97 ms 53228 KB Output is correct
14 Correct 1254 ms 53476 KB Output is correct
15 Correct 201 ms 52716 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory 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 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 314 ms 52840 KB Output is correct
12 Correct 35 ms 52076 KB Output is correct
13 Correct 97 ms 53228 KB Output is correct
14 Correct 1254 ms 53476 KB Output is correct
15 Correct 201 ms 52716 KB Output is correct
16 Correct 400 ms 135276 KB Output is correct
17 Execution timed out 1591 ms 137316 KB Time limit exceeded
18 Halted 0 ms 0 KB -