oj.uz

Submission #18071

# Submission time Handle Problem Language Result Execution time Memory
18071 2016-01-19T14:48:20 Z gs14004 OBELISK (NOI14_obelisk) C++14
25 / 25
 86 ms 2008 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 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=centx; i<=centx + 1; i++){
		for(int j=centy; j<=centy + 1; 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1744 KB Output is correct
2 Correct 0 ms 1744 KB Output is correct
3 Correct 0 ms 1744 KB Output is correct
4 Correct 0 ms 1744 KB Output is correct
5 Correct 0 ms 1744 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1744 KB Output is correct
2 Correct 0 ms 1744 KB Output is correct
3 Correct 1 ms 1744 KB Output is correct
4 Correct 0 ms 1744 KB Output is correct
5 Correct 0 ms 1744 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2008 KB Output is correct
2 Correct 78 ms 2008 KB Output is correct
3 Correct 75 ms 2008 KB Output is correct
4 Correct 74 ms 2008 KB Output is correct
5 Correct 74 ms 2008 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2008 KB Output is correct
2 Correct 73 ms 2008 KB Output is correct
3 Correct 78 ms 2008 KB Output is correct
4 Correct 86 ms 2008 KB Output is correct
5 Correct 81 ms 2008 KB Output is correct