oj.uz

Submission #364696

# Submission time Handle Problem Language Result Execution time Memory
364696 2021-02-09T17:34:46 Z Nima_Naderi Robots (APIO13_robots) C++14
100 / 100
 1140 ms 126556 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
 
const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int N=505;
 
int n, m, k, u, v, x, y, t, a, b, ans;
char A[N][N];
pii nex[4][N][N];
bool mark[4][N][N];
int dp[10][10][N][N];
bool inq[N][N];
int DX[]={0, +1, 0, -1}, DY[]={+1, 0, -1, 0};
pii tof[N*N*10];
 
pii go(int dir, int x, int y){
//	cerr<<"go "<<dir<<"  "<<x<<", "<<y<<endl;
	if (nex[dir][x][y]!=pii(0, 0)) return nex[dir][x][y];
	if (mark[dir][x][y]) return nex[dir][x][y]={-1, -1};
	mark[dir][x][y]=1;
	int dd=dir;
	if (A[x][y]=='A') dd=(dir+3)%4;
	if (A[x][y]=='C') dd=(dir+1)%4;
	int xx=x+DX[dd], yy=y+DY[dd];
	if (!xx || xx>n || !yy || yy>m || A[xx][yy]=='x') return nex[dir][x][y]={x, y};
	return nex[dir][x][y]=go(dd, xx, yy);
}
 
inline void upd(int& x, int y){ x=min(x, y);}
 
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>k>>m>>n;
	for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) cin>>A[i][j];
	for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) if (A[i][j]!='x')
		for (int d:{0, 1, 2, 3}) go(d, i, j);
	// hope nex is right
	
	memset(dp, 63, sizeof(dp));
	for (int l=k; l; l--) for (int r=l; r<=k; r++){
		for (int x=1; x<=n; x++) for (int y=1; y<=m; y++){
			if (l<r){
				for (int i=l; i<r; i++) upd(dp[l][r][x][y], dp[l][i][x][y]+dp[i+1][r][x][y]);
			}
			else if (A[x][y]=='0'+l) upd(dp[l][r][x][y], 0);
		}
		// BFS or spfa or whatever
		int tail=0, head=0;
		for (int x=1; x<=n; x++) for (int y=1; y<=m; y++) if (dp[l][r][x][y]<inf) tof[head++]={x, y};
		sort(tof, tof+head, [&](pii i, pii j){
			return dp[l][r][i.first][i.second]<dp[l][r][j.first][j.second];	
		});
		while (tail<head){
			int x=tof[tail].first, y=tof[tail].second;
			tail++;
			inq[x][y]=0;
			for (int d:{0, 1, 2, 3}) if (nex[d][x][y]!=pii(-1, -1)){
				int xx=nex[d][x][y].first, yy=nex[d][x][y].second;
				if (dp[l][r][x][y]+1<dp[l][r][xx][yy]){
					dp[l][r][xx][yy]=dp[l][r][x][y]+1;
					if (!inq[xx][yy]){
//						Q.push({xx, yy});
						tof[head++]={xx, yy};
						inq[xx][yy]=1;
					}
				}
			}
		}
	}
	ans=inf;
	for (int x=1; x<=n; x++) for (int y=1; y<=m; y++) upd(ans, dp[1][k][x][y]);
	if (ans>=inf) ans=-1;
	cout<<ans<<'\n';
	
	return 0;
}
/*
2 2 2
x1
2x
 
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 100352 KB Output is correct
2 Correct 55 ms 100204 KB Output is correct
3 Correct 55 ms 100204 KB Output is correct
4 Correct 55 ms 100332 KB Output is correct
5 Correct 56 ms 100332 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 100352 KB Output is correct
2 Correct 55 ms 100204 KB Output is correct
3 Correct 55 ms 100204 KB Output is correct
4 Correct 55 ms 100332 KB Output is correct
5 Correct 56 ms 100332 KB Output is correct
6 Correct 55 ms 100204 KB Output is correct
7 Correct 56 ms 100204 KB Output is correct
8 Correct 57 ms 100204 KB Output is correct
9 Correct 60 ms 100204 KB Output is correct
10 Correct 65 ms 100332 KB Output is correct
11 Correct 168 ms 106220 KB Output is correct
12 Correct 64 ms 105964 KB Output is correct
13 Correct 74 ms 105708 KB Output is correct
14 Correct 399 ms 109568 KB Output is correct
15 Correct 115 ms 106080 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 100352 KB Output is correct
2 Correct 55 ms 100204 KB Output is correct
3 Correct 55 ms 100204 KB Output is correct
4 Correct 55 ms 100332 KB Output is correct
5 Correct 56 ms 100332 KB Output is correct
6 Correct 55 ms 100204 KB Output is correct
7 Correct 56 ms 100204 KB Output is correct
8 Correct 57 ms 100204 KB Output is correct
9 Correct 60 ms 100204 KB Output is correct
10 Correct 65 ms 100332 KB Output is correct
11 Correct 168 ms 106220 KB Output is correct
12 Correct 64 ms 105964 KB Output is correct
13 Correct 74 ms 105708 KB Output is correct
14 Correct 399 ms 109568 KB Output is correct
15 Correct 115 ms 106080 KB Output is correct
16 Correct 135 ms 109548 KB Output is correct
17 Correct 1140 ms 126556 KB Output is correct
18 Correct 179 ms 110828 KB Output is correct
19 Correct 128 ms 109676 KB Output is correct
20 Correct 585 ms 111212 KB Output is correct