oj.uz

Submission #124746

# Submission time Handle Problem Language Result Execution time Memory
124746 2019-07-03T20:25:35 Z MoNsTeR_CuBe OBELISK (NOI14_obelisk) C++17
5 / 25
 1000 ms 24440 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long 

const int INF = numeric_limits<int>::max();

vector< vector< pair<int, int> > > holes;

vector< vector< vector< int > > > memo;

pair<int, int> start;
pair<int, int> ende;

int m,k;

int X [4] = {1,-1,0,0};
int Y[4] = {0,0,1,-1};

void generate_grid(int A, int B, vector< vector< int > > &grid){
	
	
	priority_queue< tuple<int, int, int>, vector< tuple<int, int, int> >, greater< tuple<int, int, int> > > pq;
	
	pq.push(make_tuple(0,A,B));
	
	vector< vector< bool > > visited(51, vector< bool >(51));
	
	while(!pq.empty()){
		tuple< int, int, int> tup = pq.top();
		pq.pop();
		int a = get<1>(tup);
		int b = get<2>(tup);
		if(visited[a][b]){
			continue;
		}
		visited[a][b] = true;
		for(int i = 1; i <= m; i++){
			for(int j = 0; j < 4; j++){
				if(a+i*(X[j]) <= 50 && a+i*(X[j]) > 0 && b+i*Y[j] <= 50 && b+i*Y[j] > 0){
					if(visited[a+i*(X[j])][b+i*Y[j]]) continue;
					grid[a+i*(X[j])][b+i*Y[j]] = 2+i%m+grid[a][b];
					pq.push(make_tuple(2+i%m+grid[a][b],a+i*(X[j]),b+i*Y[j]));
				}
			}
		}
	}
	
	grid[A][B] = 0;
}

int dist(int a, int b, int c, int d){
	if(m == 1) return abs(a-c)+abs(b-d);
	
	vector< vector< int > > grid(51, vector< int >(51));
	
	generate_grid(a,b, grid);
	return grid[c][d];
}

int dp(int floor, int x, int y){
	//cout << floor << ' ' << x << ' ' << y << endl;
	if(floor == 1){
		return dist(x,y,ende.first, ende.second);
	}
	
	if(memo[floor][x][y] != -1) return memo[floor][x][y];
	
	memo[floor][x][y] = INF;
	
	for(int i = 0; i < (int)holes[floor].size(); i++){
		pair<int, int> p = holes[floor][i];
		memo[floor][x][y] = min(memo[floor][x][y], dp(floor-1, p.first, p.second) + dist(p.first, p.second, x, y));
	}
	return memo[floor][x][y];
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> k >> m;
	
	cin >> start.first >> start.second;
	
	cin >> ende.first >> ende.second;
	
	holes.resize(k+1);
	
	for(int i = k; i > 1; i--){
		int q;
		cin >> q;
		
		for(int j = 0; j < q; j++){
			pair<int, int> p;
			cin >> p.first >> p.second;
			holes[i].push_back(p);
		}
	}
	memo.resize(k+1, vector< vector< int > >(51, vector< int > (51,-1)));
	
	cout << dp(k, start.first, start.second) << endl;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 2 ms 632 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 3600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 24184 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 24440 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -