Submission #18070

#	Time	Username	Problem	Language	Result	Execution time	Memory
18070		gs14004	OBELISK (NOI14_obelisk)	C++14	25 / 25	862 ms	2008 KiB

obelisk

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1e6;

int k, m;
vector<pi> crd[505];
vector<int> dp[505];

int dist(int x, int y){
	if(m == 1) return x+y;
	int ret = 1e9;
	int centx = x / (m+1), centy = y / (m+1);
	for(int i=max(centx - 5, 0); i<=centx + 5; i++){
		for(int j=max(centy - 5, 0); j<=centy + 5; j++){
			int tmp = 2 * i + 2 * j;
			if(j * (m+1) != y) tmp += abs(j*(m+1) - y) + (i == 0 ? 2 : 0);
			if(i * (m+1) != x) tmp += abs(i*(m+1) - x) + (j == 0 ? 2 : 0);
			ret = min(ret, tmp);
		}
	}
	return ret;
}

int f(int x, int y){
	if(x == 0) return 0;
	if(~dp[x][y]) return dp[x][y];
	int ret = 1e9;
	for(int j=0; j<crd[x-1].size(); j++){
		ret = min(ret, f(x-1, j) + dist(abs(crd[x-1][j].first - crd[x][y].first), abs(crd[x-1][j].second - crd[x][y].second)));
	}
	return dp[x][y] = ret;
}

int main(){
	scanf("%d %d",&k,&m);
	crd[0].resize(1); crd[k].resize(1);
	scanf("%d %d %d %d",&crd[0][0].first, &crd[0][0].second, &crd[k][0].first, &crd[k][0].second);
	for(int i=1; i<k; i++){
		int t;
		scanf("%d",&t);
		crd[i].resize(t);
		for(int j=0; j<t; j++){
			scanf("%d %d",&crd[i][j].first, &crd[i][j].second);
		}
	}
	for(int i=0; i<=k; i++){
		dp[i].resize(crd[i].size(), -1);
	}
	printf("%d",f(k, 0));
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 7 / 7