oj.uz

Submission #51256

# Submission time Handle Problem Language Result Execution time Memory
51256 2018-06-17T10:28:00 Z BrunoPloumhans OBELISK (NOI14_obelisk) C++14
25 / 25
 105 ms 3412 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) {
  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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 476 KB Output is correct
3 Correct 2 ms 548 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 3 ms 620 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 708 KB Output is correct
2 Correct 3 ms 708 KB Output is correct
3 Correct 4 ms 784 KB Output is correct
4 Correct 4 ms 784 KB Output is correct
5 Correct 3 ms 784 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 784 KB Output is correct
2 Correct 85 ms 876 KB Output is correct
3 Correct 92 ms 1056 KB Output is correct
4 Correct 77 ms 1264 KB Output is correct
5 Correct 91 ms 1452 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 1452 KB Output is correct
2 Correct 85 ms 1908 KB Output is correct
3 Correct 86 ms 2404 KB Output is correct
4 Correct 92 ms 3024 KB Output is correct
5 Correct 89 ms 3412 KB Output is correct