제출 #18068

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
18068		gs14004	오벨리스크 (NOI14_obelisk)	C++14	5 / 25	0 ms	1744 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){
	return x + y;
}

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: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 7