Submission #125118

#	Time	Username	Problem	Language	Result	Execution time	Memory
125118		MoNsTeR_CuBe	OBELISK (NOI14_obelisk)	C++17	5 / 25	35 ms	24056 KiB

obelisk

#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};
 
int calc(int a){
	if(a%(m+1) == 0) return 2*(a/(m+1));
	return (a%(m+1))+2*(a/(m+1)+1);
}
 
int dist(int a, int b, int c, int d){
	if(m == 1) return abs(a-c)+abs(b-d);
	
	return calc(abs(a-c))+calc(abs(b-d));
}
 
int dp(int floor, int x, int y){
	//cout << floor << ' ' << x << ' ' << y << endl;
	if(floor == 1){
		//cout << x << ' ' << y << ' ' << ende.first << " " << ende.second << ' ' << dist(x,y,ende.first, ende.second) << endl;
		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 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 7