oj.uz

Submission #240594

# Submission time Handle Problem Language Result Execution time Memory
240594 2020-06-20T07:27:54 Z alishahali1382 Robots (APIO13_robots) C++14
60 / 100
 415 ms 163840 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*2];
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 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 62 ms 100220 KB Output is correct
2 Correct 55 ms 100216 KB Output is correct
3 Correct 62 ms 100216 KB Output is correct
4 Correct 56 ms 100320 KB Output is correct
5 Correct 57 ms 100344 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 100220 KB Output is correct
2 Correct 55 ms 100216 KB Output is correct
3 Correct 62 ms 100216 KB Output is correct
4 Correct 56 ms 100320 KB Output is correct
5 Correct 57 ms 100344 KB Output is correct
6 Correct 56 ms 100216 KB Output is correct
7 Correct 56 ms 100216 KB Output is correct
8 Correct 63 ms 100216 KB Output is correct
9 Correct 63 ms 100216 KB Output is correct
10 Correct 54 ms 100344 KB Output is correct
11 Correct 151 ms 106352 KB Output is correct
12 Correct 63 ms 106104 KB Output is correct
13 Correct 93 ms 105720 KB Output is correct
14 Correct 370 ms 109688 KB Output is correct
15 Correct 123 ms 106104 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 100220 KB Output is correct
2 Correct 55 ms 100216 KB Output is correct
3 Correct 62 ms 100216 KB Output is correct
4 Correct 56 ms 100320 KB Output is correct
5 Correct 57 ms 100344 KB Output is correct
6 Correct 56 ms 100216 KB Output is correct
7 Correct 56 ms 100216 KB Output is correct
8 Correct 63 ms 100216 KB Output is correct
9 Correct 63 ms 100216 KB Output is correct
10 Correct 54 ms 100344 KB Output is correct
11 Correct 151 ms 106352 KB Output is correct
12 Correct 63 ms 106104 KB Output is correct
13 Correct 93 ms 105720 KB Output is correct
14 Correct 370 ms 109688 KB Output is correct
15 Correct 123 ms 106104 KB Output is correct
16 Correct 159 ms 109816 KB Output is correct
17 Runtime error 415 ms 163840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -