Advertisement
erek1e

IOI '04 P2 - Hermes

Jul 20th, 2022
709
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.09 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int MX = 2001;
  8. const int INF = 1e8;
  9.  
  10. struct Point {
  11.     int x, y;
  12. };
  13. int vertical[2][MX], horizontal[2][MX]; // vertical and horizontal
  14. /* v[y] = min moves to deliver all messages in current prefix and end up at point with y coordinate
  15. at y and x coordinate being the same as x of last point in prefix. Vice versa with h[x] */
  16.  
  17. const int startX = 1000, startY = 1000;
  18.  
  19. int main() {
  20.     int n; cin >> n;
  21.     vector<Point> points(n);
  22.     for (Point &p : points) {
  23.         cin >> p.x >> p.y;
  24.         p.x += startX, p.y += startY;
  25.     }
  26.     points.insert(points.begin(), {startX, startY});
  27.     for (int i = 0; i < MX; ++i) vertical[0][i] = horizontal[0][i] = INF;
  28.     vertical[0][startY] = horizontal[0][startX] = 0;
  29.  
  30.     for (int i = 1; i <= n; ++i) {
  31.         Point p1 = points[i-1], p = points[i];
  32.         int *v1 = vertical[(i-1)&1], *h1 = horizontal[(i-1)&1]; // previous dp states
  33.         int *v = vertical[i&1], *h = horizontal[i&1]; // next dp states
  34.         for (int j = 0; j < MX; ++j) v[j] = h[j] = INF;
  35.  
  36.         // calculate h
  37.         for (int x = 0; x < MX; ++x) {
  38.             if (x == p.x) continue;
  39.             if (x == p1.x) {
  40.                 for (int y = 0; y < MX; ++y) {
  41.                     h[x] = min(h[x], v1[y] + abs(p.y-y));
  42.                 }
  43.             } else {
  44.                 h[x] = h1[x] + abs(p.y-p1.y);
  45.             }
  46.         }
  47.  
  48.         // calculate v
  49.         for (int y = 0; y < MX; ++y) {
  50.             if (y == p.y) continue;
  51.             if (y == p1.y) {
  52.                 for (int x = 0; x < MX; ++x) {
  53.                     v[y] = min(v[y], h1[x] + abs(p.x-x));
  54.                 }
  55.             } else {
  56.                 v[y] = v1[y] + abs(p.x-p1.x);
  57.             }
  58.         }
  59.  
  60.         // calculate for the point itself
  61.         if (p.y == p1.y) h[p.x] = v[p.y] = h1[p.x];
  62.         else if (p.x == p1.x) h[p.x] = v[p.y] = v1[p.y];
  63.     }
  64.  
  65.     int *v = vertical[n&1], *h = horizontal[n&1];
  66.     cout << min(*min_element(v, v+MX), *min_element(h, h+MX)) << endl;
  67.     return 0;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement