oj.uz

Submission #705758

# Submission time Handle Problem Language Result Execution time Memory
705758 2023-03-05T06:43:43 Z hoangnghiep Robots (APIO13_robots) C++14
60 / 100
 243 ms 163840 KB 
#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define repeat(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define p push
#define pii pair<int,int>
#define piii pair<int,pair<int,int>>
#define vii vector<vector<int>>
#define vi vector<int>
//#define DEBUG
//#define multipletest
using namespace std;
const int LIM=5e2;
const int mod=1e9+7;
const int maxn=20;
const int inf=1e9;
int n,m,x,y,t,num,e,q,w,h;
int dx[8]={-1,0,1,0,-1,-1,1,1};
int dy[8]={0,1,0,-1,1,-1,1,-1};
char c;
int dp[10][10][LIM+5][LIM+5];
vector<pii> memodfs[LIM+5][LIM+5];
bool vis[LIM+5][LIM+5];
vector<pii> dist[LIM*LIM+5];
char grid[LIM+5][LIM+5];
bool check(int x,int y){
    if(x<=0 || x>n || y<=0 || y>m || grid[x][y]=='x'){
   return false;
     }
    return true;
}
pii dfs(int i,int j,int k){
	while(true){
	    if(grid[i][j]=='C'){
	    	k=(k+1)%4;
		}
		else if(grid[i][j]=='A'){
			k=(k+3)%4;
		}
		int x=i+dx[k];
		int y=j+dy[k];
		if(check(x,y)==false) return {i,j};
		i=x,j=y;
	}
}
void bfs(int l,int r){
	   // cout<<"bfs "<<l<<" "<<r<<endl;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			vis[i][j]=false;
		}
	}
	for(int i=0;i<=n*m+5;++i){
		dist[i].clear();
	}
	int mn=inf;
	int mx=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(dp[l][r][i][j]!=-1){
				dist[dp[l][r][i][j]].push_back({i,j});
				mn=min(mn,dp[l][r][i][j]);
				mx=max(mx,dp[l][r][i][j]);
			}
		}
	}
	for(int i=0;i<=n*m+5;++i){
		for(auto tmp:dist[i]){
			int x=tmp.f;
			int y=tmp.s;
			if(vis[x][y]) continue;
			vis[x][y]=1;
			for(auto nxt:memodfs[x][y]){
				int nx=nxt.f;
				int ny=nxt.s;
				if((dp[l][r][nx][ny]>dp[l][r][x][y]+1) || dp[l][r][nx][ny]==-1){
					dp[l][r][nx][ny]=dp[l][r][x][y]+1;
					dist[dp[l][r][nx][ny]].push_back({nx,ny});
				}
			}
		}
	}
}
void solve(){
//Sieve();
//   precal();
    #ifdef interactive
    testcase();
    #endif
    cin>>num>>m>>n;
    for(int i=0;i<10;++i){
    	for(int j=0;j<10;++j){
    		for(int k=1;k<=n;++k){
    			for(int l=1;l<=m;++l){
    				dp[i][j][k][l]=-1;
				}
			}
		}
	}
    for(int i=1;i<=n;++i){
    	for(int j=1;j<=m;++j){
    		cin>>grid[i][j];
    		if('0'<=grid[i][j] && grid[i][j]<='9'){
    			 x=grid[i][j]-'0';
    			dp[x][x][i][j]=0;
			}
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			for(int k=0;k<4;++k){
				memodfs[i][j].push_back(dfs(i,j,k));
			}
		}
	}
	for(int d=0;d<num;++d){
		for(int l=1;l+d<=num;++l){
			int r=l+d;
			for(int mid=l;mid<r;++mid){
				for(int i=1;i<=n;++i){
					for(int j=1;j<=m;++j){
						if((dp[l][r][i][j]==-1 || dp[l][r][i][j]>dp[l][mid][i][j]+dp[mid+1][r][i][j]) 
						&& (dp[l][mid][i][j]!=-1 && dp[mid+1][r][i][j]!=-1)){
							dp[l][r][i][j]=dp[l][mid][i][j] + dp[mid+1][r][i][j];
						}
					}
				}
			}
			bfs(l,r);
		}
	}
	int ans=inf;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
		if(dp[1][num][i][j]!=-1)	ans = min(ans,dp[1][num][i][j]);
		}
	}
	if(ans==inf) cout<<-1<<endl;
	else cout<<ans<<endl;
}
signed main(){
  // freopen(".inp","r",stdin);
  // freopen(".out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int test;
	test=1;
	#ifdef multipletest
	cin>>test;
	#endif
	while(test--){
        solve();
        #ifdef DEBUG
		cerr << "Runtime is: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
	    #endif
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12984 KB Output is correct
2 Correct 7 ms 12884 KB Output is correct
3 Correct 7 ms 12884 KB Output is correct
4 Correct 9 ms 16468 KB Output is correct
5 Correct 10 ms 16520 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12984 KB Output is correct
2 Correct 7 ms 12884 KB Output is correct
3 Correct 7 ms 12884 KB Output is correct
4 Correct 9 ms 16468 KB Output is correct
5 Correct 10 ms 16520 KB Output is correct
6 Correct 7 ms 13340 KB Output is correct
7 Correct 7 ms 12884 KB Output is correct
8 Correct 7 ms 13652 KB Output is correct
9 Correct 7 ms 13268 KB Output is correct
10 Correct 9 ms 16468 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12984 KB Output is correct
2 Correct 7 ms 12884 KB Output is correct
3 Correct 7 ms 12884 KB Output is correct
4 Correct 9 ms 16468 KB Output is correct
5 Correct 10 ms 16520 KB Output is correct
6 Correct 7 ms 13340 KB Output is correct
7 Correct 7 ms 12884 KB Output is correct
8 Correct 7 ms 13652 KB Output is correct
9 Correct 7 ms 13268 KB Output is correct
10 Correct 9 ms 16468 KB Output is correct
11 Correct 148 ms 144348 KB Output is correct
12 Correct 79 ms 138408 KB Output is correct
13 Correct 111 ms 138592 KB Output is correct
14 Correct 243 ms 154932 KB Output is correct
15 Correct 131 ms 139588 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12984 KB Output is correct
2 Correct 7 ms 12884 KB Output is correct
3 Correct 7 ms 12884 KB Output is correct
4 Correct 9 ms 16468 KB Output is correct
5 Correct 10 ms 16520 KB Output is correct
6 Correct 7 ms 13340 KB Output is correct
7 Correct 7 ms 12884 KB Output is correct
8 Correct 7 ms 13652 KB Output is correct
9 Correct 7 ms 13268 KB Output is correct
10 Correct 9 ms 16468 KB Output is correct
11 Correct 148 ms 144348 KB Output is correct
12 Correct 79 ms 138408 KB Output is correct
13 Correct 111 ms 138592 KB Output is correct
14 Correct 243 ms 154932 KB Output is correct
15 Correct 131 ms 139588 KB Output is correct
16 Runtime error 72 ms 163840 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -