| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 5286 |
2014-03-15T19:04:33 Z |
ainta |
OBELISK (NOI14_obelisk) |
C++ |
|
0 ms |
1964 KB |
#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;
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;
}
else{
t = (a.x - b.x) / (L + 1);
a.x -= t*(L + 1), s += t * 2;
}
if (a.y < b.y){
t = (b.y - a.y) / (L + 1);
a.y += t*(L + 1), s += t * 2;
}
else{
t = (a.y - b.y) / (L + 1);
a.y -= t*(L + 1), s += t * 2;
}
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) t += 2;
if (b.y != a.y && !i) 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", &L, &K);
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]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
1964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
