제출 #51252

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51252		BrunoPloumhans	오벨리스크 (NOI14_obelisk)	C++14	0 / 25	95 ms	1204 KiB

obelisk

#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
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 7