Submission #51256

#	Time	Username	Problem	Language	Result	Execution time	Memory
51256		BrunoPloumhans	OBELISK (NOI14_obelisk)	C++14	25 / 25	105 ms	3412 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) {
  if(m == 1) {
    //printf("dist(%lld, %lld, %lld, %lld) => %lld\n", x1, y1, x2, y2, abs(x1-x2) + abs(y1-y2));
    return abs(x1-x2) + abs(y1-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;
  vector<hole> prev(1, hole({42, 42, 0}));
  vector<hole> curr;
  cin >> prev[0].x >> prev[0].y;
  cin >> ex >> ey;

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