oj.uz

Submission #369443

# Submission time Handle Problem Language Result Execution time Memory
369443 2021-02-21T16:57:24 Z YJU Robots (APIO13_robots) C++14
30 / 100
 1500 ms 107744 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[11][11][N][N],dis[N][N][2][5];
//dp[l][r][x][y] 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);
	//prepare
	REP(ii,10)REP(jj,10)REP(i,N)REP(j,N)dp[ii][jj][i][j]=INF;
	//prepare end
	
	//input
	cin>>n>>C>>R;
	REP1(i,R)cin>>grid[i],grid[i]="x"+grid[i];
	//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[l][r][i][j]=(grid[i][j]-'0'==l?0:INF);
				}else{
					for(int cut=l;cut+1<=r;cut++){
						dp[l][r][i][j]=min(dp[l][r][i][j],dp[l][cut][i][j]+dp[cut+1][r][i][j]);
					}
				}
				//
				dis[i][j][0][0]=dp[l][r][i][j];
				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){
						//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";
			REP1(i,R)REP1(j,C){
				dp[l][r][i][j]=min(dp[l][r][i][j],dis[i][j][0][0]);
				//cout<<setw(2)<<(dp[l][r][i][j]==INF?-1:dp[l][r][i][j])<<(j==C?"\n":" ");
			}
		}
	}
	ll ans=INF;
	REP1(i,R)REP1(j,C){
		ans=min(ans,dp[1][n][i][j]);
	}
	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 55 ms 100204 KB Output is correct
2 Correct 58 ms 100332 KB Output is correct
3 Correct 55 ms 100332 KB Output is correct
4 Correct 55 ms 100332 KB Output is correct
5 Correct 57 ms 100332 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 100204 KB Output is correct
2 Correct 58 ms 100332 KB Output is correct
3 Correct 55 ms 100332 KB Output is correct
4 Correct 55 ms 100332 KB Output is correct
5 Correct 57 ms 100332 KB Output is correct
6 Correct 57 ms 100332 KB Output is correct
7 Correct 55 ms 100204 KB Output is correct
8 Correct 66 ms 100352 KB Output is correct
9 Correct 59 ms 100204 KB Output is correct
10 Correct 57 ms 100332 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 100204 KB Output is correct
2 Correct 58 ms 100332 KB Output is correct
3 Correct 55 ms 100332 KB Output is correct
4 Correct 55 ms 100332 KB Output is correct
5 Correct 57 ms 100332 KB Output is correct
6 Correct 57 ms 100332 KB Output is correct
7 Correct 55 ms 100204 KB Output is correct
8 Correct 66 ms 100352 KB Output is correct
9 Correct 59 ms 100204 KB Output is correct
10 Correct 57 ms 100332 KB Output is correct
11 Correct 1041 ms 107744 KB Output is correct
12 Correct 73 ms 104940 KB Output is correct
13 Correct 476 ms 105196 KB Output is correct
14 Execution timed out 1558 ms 106468 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 100204 KB Output is correct
2 Correct 58 ms 100332 KB Output is correct
3 Correct 55 ms 100332 KB Output is correct
4 Correct 55 ms 100332 KB Output is correct
5 Correct 57 ms 100332 KB Output is correct
6 Correct 57 ms 100332 KB Output is correct
7 Correct 55 ms 100204 KB Output is correct
8 Correct 66 ms 100352 KB Output is correct
9 Correct 59 ms 100204 KB Output is correct
10 Correct 57 ms 100332 KB Output is correct
11 Correct 1041 ms 107744 KB Output is correct
12 Correct 73 ms 104940 KB Output is correct
13 Correct 476 ms 105196 KB Output is correct
14 Execution timed out 1558 ms 106468 KB Time limit exceeded
15 Halted 0 ms 0 KB -