oj.uz

Submission #51252

# Submission time Handle Problem Language Result Execution time Memory
51252 2018-06-17T10:16:18 Z BrunoPloumhans OBELISK (NOI14_obelisk) C++14
0 / 25
 95 ms 1204 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int INF = 1000000000000000000;

int k, m;

int dist(int x1, int y1, int x2, int y2) {
  int ret = INF;
  for(int i = 0; i < 2; ++i) {
    for(int j = 0; j < 2; ++j) {
      int dx = abs(x1-x2), dy = abs(y1-y2);	
      int fullx = dx/(m+1)+i;
      int fully = dy/(m+1)+j;
      int ans = 2*fullx + 2*fully;
      
      int leftx = abs(dx - fullx*(m+1)), lefty = abs(dy - fully*(m+1));
      ans += leftx + lefty;
      if(fullx == 0 && lefty > 0) {
	ans += 2;
      }
      if(fully == 0 && leftx > 0) {
	ans += 2;
      }
      ret = min(ret, ans);
    }
  }
  //printf("dist(%lld, %lld, %lld, %lld) => %lld\n", x1, y1, x2, y2, ret);
  return ret;
}

struct hole {
  int x, y;
  int cost;
};

signed main() {
  cin >> k >> m;
  int ex, ey;
  cin >> ex >> ey;
  vector<hole> prev(1, hole({42, 42, 0}));
  vector<hole> curr;
  cin >> prev[0].x >> prev[0].y;
  for(int i = k-1; i >= 0; --i) {
    int h;
    if(i == 0) h = 1;
    else cin >> h;
    curr.resize(h);
    if(i == 0) curr[0] = hole({ex, ey, INF});
    else {
      for(hole& ho : curr) {
	cin >> ho.x >> ho.y;
	ho.cost = INF;
      }
    }
    for(hole p : prev) {
      for(hole& c : curr) {
	c.cost = min(c.cost, p.cost + dist(p.x, p.y, c.x, c.y));
      }
    }
    swap(prev, curr);
  }
  cout << prev[0].cost << endl;
  return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 6.0

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

Subtask #4
0 / 7.0

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