oj.uz

Submission #18068

# Submission time Handle Problem Language Result Execution time Memory
18068 2016-01-19T14:13:30 Z gs14004 OBELISK (NOI14_obelisk) C++14
5 / 25
 0 ms 1744 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){
	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.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
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #4
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -