oj.uz

Submission #240590

# Submission time Handle Problem Language Result Execution time Memory
240590 2020-06-20T07:21:33 Z alishahali1382 Robots (APIO13_robots) C++14
30 / 100
 1500 ms 106104 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};
queue<pii> Q;

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
		for (int x=1; x<=n; x++) for (int y=1; y<=m; y++) if (dp[l][r][x][y]<inf) Q.push({x, y});
		while (Q.size()){
			int x=Q.front().first, y=Q.front().second;
			Q.pop();
			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});
						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 56 ms 100216 KB Output is correct
2 Correct 56 ms 100216 KB Output is correct
3 Correct 61 ms 100216 KB Output is correct
4 Correct 56 ms 100344 KB Output is correct
5 Correct 55 ms 100344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 100216 KB Output is correct
2 Correct 56 ms 100216 KB Output is correct
3 Correct 61 ms 100216 KB Output is correct
4 Correct 56 ms 100344 KB Output is correct
5 Correct 55 ms 100344 KB Output is correct
6 Correct 57 ms 100344 KB Output is correct
7 Correct 55 ms 100216 KB Output is correct
8 Correct 55 ms 100216 KB Output is correct
9 Correct 58 ms 100216 KB Output is correct
10 Correct 57 ms 100344 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 100216 KB Output is correct
2 Correct 56 ms 100216 KB Output is correct
3 Correct 61 ms 100216 KB Output is correct
4 Correct 56 ms 100344 KB Output is correct
5 Correct 55 ms 100344 KB Output is correct
6 Correct 57 ms 100344 KB Output is correct
7 Correct 55 ms 100216 KB Output is correct
8 Correct 55 ms 100216 KB Output is correct
9 Correct 58 ms 100216 KB Output is correct
10 Correct 57 ms 100344 KB Output is correct
11 Execution timed out 1600 ms 106104 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 100216 KB Output is correct
2 Correct 56 ms 100216 KB Output is correct
3 Correct 61 ms 100216 KB Output is correct
4 Correct 56 ms 100344 KB Output is correct
5 Correct 55 ms 100344 KB Output is correct
6 Correct 57 ms 100344 KB Output is correct
7 Correct 55 ms 100216 KB Output is correct
8 Correct 55 ms 100216 KB Output is correct
9 Correct 58 ms 100216 KB Output is correct
10 Correct 57 ms 100344 KB Output is correct
11 Execution timed out 1600 ms 106104 KB Time limit exceeded
12 Halted 0 ms 0 KB -