oj.uz

Submission #369507

# Submission time Handle Problem Language Result Execution time Memory
369507 2021-02-21T18:59:20 Z YJU Robots (APIO13_robots) C++14
100 / 100
 1301 ms 146060 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;
	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++){
			vector<vector<pll> > lis;
			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){
					lis.resize(max(SZ(lis),dis[i][j]+1));
					lis[dis[i][j]].pb(mp(i,j));
					//pq.push(node(dis[i][j],i,j));
				}
				//
			}
			//moving robots
			for(ll k=0;k<SZ(lis);k++){
				for(pll nd:lis[k]){
					if(dis[nd.X][nd.Y]<k)continue;
					dp[nd.X][nd.Y][l][r]=min(dp[nd.X][nd.Y][l][r],dis[nd.X][nd.Y]);
					REP1(dir,4){
						pll nxt=nxt_state[nd.X][nd.Y][dir];
						if(nxt==mp(-1,-1))continue;
						if(dis[nxt.X][nxt.Y]>k+1){
							dis[nxt.X][nxt.Y]=k+1;
							lis.resize(max(SZ(lis),k+1+1));
							lis[k+1].pb(nxt);
						}
					}
				}
				lis[k].clear();
			}
		}
	}
	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 1 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

# 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 1 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 1 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
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 1 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 1 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 245 ms 53472 KB Output is correct
12 Correct 33 ms 49576 KB Output is correct
13 Correct 92 ms 49792 KB Output is correct
14 Correct 435 ms 53472 KB Output is correct
15 Correct 177 ms 50476 KB Output is correct

Subtask #4
40.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 1 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 1 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 245 ms 53472 KB Output is correct
12 Correct 33 ms 49576 KB Output is correct
13 Correct 92 ms 49792 KB Output is correct
14 Correct 435 ms 53472 KB Output is correct
15 Correct 177 ms 50476 KB Output is correct
16 Correct 390 ms 131436 KB Output is correct
17 Correct 1301 ms 146060 KB Output is correct
18 Correct 494 ms 136116 KB Output is correct
19 Correct 376 ms 131492 KB Output is correct
20 Correct 931 ms 142368 KB Output is correct