oj.uz

답안 #18069

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18069 2016-01-19T14:42:12 Z gs14004 오벨리스크 (NOI14_obelisk) C++14
12 / 25
 38 ms 2016 KB 
#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 dp2[55][55];

int dist(int x, int y){
	if(m == 1) return x+y;
	if(dp2[x][y]) return dp2[x][y];
	int ret = 1e9;
	for(int i=0; i<60; i++){
		for(int j=0; j<60; 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 dp2[x][y] = 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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1756 KB Output is correct
2 Correct 0 ms 1756 KB Output is correct
3 Correct 0 ms 1756 KB Output is correct
4 Correct 0 ms 1756 KB Output is correct
5 Correct 0 ms 1756 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 1756 KB Output is correct
2 Correct 32 ms 1756 KB Output is correct
3 Correct 36 ms 1756 KB Output is correct
4 Correct 38 ms 1756 KB Output is correct
5 Correct 31 ms 1756 KB Output is correct

Subtask #3
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 23 ms 2016 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -