Submission #5290

#	Time	Username	Problem	Language	Result	Execution time	Memory
5290		ainta	OBELISK (NOI14_obelisk)	C++98	25 / 25	156 ms	1964 KiB

obelisk

#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
#define INF 99999999999999LL
using namespace std;
struct point{
	int x, y;
}w[510][110];
int C[510], L;
long long D[510][110];
long long F(point a, point b){
	if (L == 1)return abs(a.x - b.x) + abs(a.y - b.y);
	int i, j, ck1 = 0, ck2 = 0;
	long long s = 0, res = INF, t;
	if (a.x < b.x){
		t = (b.x - a.x) / (L + 1);
		a.x += t*(L + 1), s += t * 2;
		if(t)ck1 = 1;
	}
	else{
		t = (a.x - b.x) / (L + 1);
		a.x -= t*(L + 1), s += t * 2;
		if(t)ck1 = 1;
	}
	if (a.y < b.y){
		t = (b.y - a.y) / (L + 1);
		a.y += t*(L + 1), s += t * 2;
		if (t)ck2 = 1;
	}
	else{
		t = (a.y - b.y) / (L + 1);
		a.y -= t*(L + 1), s += t * 2;
		if (t)ck2 = 1;
	}
	for (i = -1; i <= 1; i++){
		for (j = -1; j <= 1; j++){
			a.x += i*(L + 1), a.y += j*(L + 1);
			t = s + abs(b.x - a.x) + abs(b.y - a.y) + abs(i) * 2 + abs(j) * 2;
			if (b.x != a.x && !j && !ck2) t += 2;
			if (b.y != a.y && !i && !ck1) t += 2;
			if (res > t)res = t;
			a.x -= i*(L + 1), a.y -= j*(L + 1);
		}
	}
	return res;
}
void Do(int x){
	int i, j;
	long long t;
	for (i = 0; i < C[x + 1]; i++)D[x + 1][i] = INF;
	for (i = 0; i < C[x]; i++){
		for (j = 0; j < C[x + 1]; j++){
			t = F(w[x][i], w[x + 1][j]) + D[x][i];
			if (D[x + 1][j] > t)D[x + 1][j] = t;
		}
	}
}
int main()
{
	int i, K, j;
	scanf("%d%d", &K, &L);
	C[0] = C[K] = 1;
	scanf("%d%d%d%d", &w[0][0].x, &w[0][0].y, &w[K][0].x, &w[K][0].y);
	for (i = 1; i <= K; i++){
		if (i != K){
			scanf("%d", &C[i]);
			for (j = 0; j < C[i]; j++){
				scanf("%d%d", &w[i][j].x, &w[i][j].y);
			}
		}
		Do(i - 1);
	}
	printf("%lld\n", D[K][0]);
}

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